A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.

Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]


Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer &gt;= 1 and &lt;= 10.


Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s consists of only digits and does not contain leading zeros.
	1 &lt;= k &lt;= 109


"""
                                "1317"
[1, 3, 1, 7]        -> [1] * nums(317, k)
[1, 3, 17]         
[1, 31, 7]
[1, 317]   
[13, 1, 7]          -> [13] * nums(17, k)
[13, 17]
[131, 7]
[1317]


                            "2020"    k = 30
[2000] x
[2, 020] x
[20, 20]

                            "67890" k = 90

[6, 7890] x
[6, 7, 8, 9, 0] x
[6, 7, 8, 90]   OK
[6, 78, 90]     OK
[67, 8, 90]     OK
[67, 89, 0] x
[678, 90] x
break because 678 > k (90), so neither 678, 6789 would be possible numbers

"""



class Solution:
    def num_arrays(self, s, k, memo):
        if not s:
            return 0
        memo_ans = memo.get(s)
        if memo_ans is not None:
            return memo_ans
        
        num = int(s)
        if num <= k:
            counter = 1
        else:
            counter = 0
    
        for i in range(len(s) - 1):
            # Stop when the number to the right side of the array is greater than k
            if int(s[:i + 1]) > k:
                break
            # Don't count leading zeros
            if s[i + 1] == "0":
                continue
            counter += self.num_arrays(s[i + 1:], k, memo)
        ans = counter % (10 ** 9 + 7)
        memo[s] = ans
        return ans
    
    def numberOfArrays(self, s: str, k: int) -> int:
        memo = {}
        return self.num_arrays(s, k, memo)
class Solution {
    static long mod;
    private long solve(int idx,String s,int k,long[] dp){
        if(idx==s.length())
            return 1;
        if(dp[idx]!=-1)
            return dp[idx];
        long max=0,number=0;
        for(int i=idx;i<s.length();i++){
            int temp=s.charAt(i)-'0';
            number=(number*10)+temp;
            if(number>=1 && number<=k){
                max=(max+solve(i+1,s,k,dp))%mod;
            }else
                break;
        }
        return dp[idx]=max;
    }
    public int numberOfArrays(String s, int k) {
        mod = (int)1e9+7;
        long[] dp=new long[s.length()+1];
        Arrays.fill(dp,-1);
        return (int)solve(0,s,k,dp);
    }
}
class Solution {
public:
    int mod=1e9+7;
    int f(int i,int k,string &s,vector<int> &dp){
        if(i==s.size()) return 1;//empty string
        if(dp[i]!=-1) return dp[i];//Memoization step
        if(s[i]=='0') return 0;//leading zeroes
        long long num=0;
        int ans=0;
        for(int j=i;j<s.size();j++){
            num=num*10+s[j]-'0';
            if(num>k) break;
            ans+=f(j+1,k,s,dp);//create num and call for next index
            ans%=mod;
        }
        return dp[i]=ans;//storing answer
    }
    int numberOfArrays(string s, int k) {
        int n=s.size();
        vector<int> dp(n+1,-1);
        return f(0,k,s,dp);
        // dp[i]=total ways to
        // create possible arrays starting at index i
    }
};
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var numberOfArrays = function(s, k) {
    var cache={};
    return backtrack(0)%1000000007;
    function backtrack(pos){
        let orignalPos = pos;
        if(cache[pos]!==undefined){
            return cache[pos];
        }
        let count=0;
        let digit=0;
        while(pos<s.length){
            digit = digit*10 + parseInt(s[pos]);
            if(digit<=k && pos+1<=s.length-1 && s[pos+1]!=='0'){//If we can call backtrack on next position. 
                count+=(backtrack(pos+1)%1000000007);
            }
            if(digit>k){
                break;
            }
            pos++;
        }    
        if(pos===s.length && digit<=k){//If this number became the only digit in the array, for string starting at position orignalPos. This also completed the etire string. 
            count++;
        }
        cache[orignalPos]=count;
        return count;
    }
};
Restore The Array