1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
def df(l, r, s, k, dict_):
    if (l, r, s) in dict_:
        return dict_[(l, r, s)]
    f = min(k, 9)
    if s < 50000:
        dp = [[0 for i in range(f + 1)] for i in range(s)]
        for i in range(s):
            for j in range(f + 1):
                if i == 0 and j == l:
                    dp[i][j] = 1
                elif i == 0:
                    dp[i][j] = 0
                else:
                    ans = 0
                    for ff in range(f + 1):
                        if j * ff <= k:
                            ans += dp[i - 1][ff] % (10 ** 9 + 7)
                    dp[i][j] = ans % (10 ** 9 + 7)
        ans = dp[s - 1][r]
        dict_[(l, r, s)] = ans
        return  ans
    ans = 0
    s1 = s / 2 + 1
    s2 = s - s1 + 1
    for i in range(f + 1):
        ans += df(l, i, s1, k, dict_) * df(i, r, s2, k, dict_)
    dict_[(l, r, s)] = ans % (10 ** 9 + 7)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX