1
class Solution {
2
 public:
3
  int mod = 1e9 + 7;
4
  int f(int i, int k, string &s, vector<int> &dp) {
5
    if (i == s.size()) return 1;   // empty string
6
    if (dp[i] != -1) return dp[i]; // Memoization step
7
    if (s[i] == '0') return 0;     // leading zeroes
8
    long long num = 0;
9
    int ans = 0;
10
    for (int j = i; j < s.size(); j++) {
11
      num = num * 10 + s[j] - '0';
12
      if (num > k) break;
13
      ans += f(j + 1, k, s, dp); // create num and call for next index
14
      ans %= mod;
15
    }
16
    return dp[i] = ans; // storing answer
17
  }
18
  int numberOfArrays(string s, int k) {
19
    int n = s.size();
20
    vector<int> dp(n + 1, -1);
21
    return f(0, k, s, dp);
22
    // dp[i]=total ways to
23
    // create possible arrays starting at index i
24
  }
25
};