Untitled

class Solution {
    private static final int MOD = 1_000_000_007;

    public int numberOfArrays(String s, int k) {
        int n = s.length();
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        return countWays(s, 0, k, memo);
    }

    private int countWays(String s, int index, int k, int[] memo) {
        // Base case: if we've processed the entire string
        if (index == s.length()) return 1;

        // If the current index has already been computed
        if (memo[index] != -1) return memo[index];

        // If the segment starts with '0', it's invalid
        if (s.charAt(index) == '0') return 0;

        long currentNumber = 0;
        int ways = 0;

        // Try forming numbers by taking substrings starting at `index`
        for (int i = index; i < s.length(); i++) {
            currentNumber = currentNumber * 10 + (s.charAt(i) - '0'); // Form the number

            // If the number is greater than `k`, break the loop
            if (currentNumber > k) break;

            // If the number is valid, recursively process the remaining string
            ways = (ways + countWays(s, i + 1, k, memo)) % MOD;
        }

        // Store the result for the current index in the memoization array
        memo[index] = ways;
        return ways;
    }
}