1
class Solution {
2
  static long mod;
3

4
  private long solve(int idx, String s, int k, long[] dp) {
5
    if (idx == s.length()) return 1;
6
    if (dp[idx] != -1) return dp[idx];
7
    long max = 0, number = 0;
8
    for (int i = idx; i < s.length(); i++) {
9
      int temp = s.charAt(i) - '0';
10
      number = (number * 10) + temp;
11
      if (number >= 1 && number <= k) {
12
        max = (max + solve(i + 1, s, k, dp)) % mod;
13
      } else break;
14
    }
15
    return dp[idx] = max;
16
  }
17

18
  public int numberOfArrays(String s, int k) {
19
    mod = (int) 1e9 + 7;
20
    long[] dp = new long[s.length() + 1];
21
    Arrays.fill(dp, -1);
22
    return (int) solve(0, s, k, dp);
23
  }
24
}