Problem Description

The substring "1001" of $ square1001 $ has a very small sum of its digits, $ 1+0+0+1=2 $.

Even if you split "1001" into parts like {$ 1,0,01 $} or {$ 1,001 $}, the sums are still very small, $ 1+0+1=2 $ and $ 1+1=2 $ respectively.

"1001" is a very mysterious number. He decided to think about it.

When splitting an integer $ n $, the sum must not exceed $ D $.

Here, the definition of "splitting" is as follows:

• Consider the integer $ N $ as a string, denoted as $ S $.
• Split $ S $ into several parts.
• For example, "1234567" can be split into {$ "1","234567" $}, {$ "12","34","56","7" $}, or {$ "1234567" $}, etc.
• Treat each part as a number.
• For example, "1234" can be considered as the number $ 1234 $.
• Each part may start with zero.

For example, there are $ 3 $ ways to split "1355" such that the sum is less than or equal to 50:

Split MethodSum1+3+5+51413+5+5231+35+541Count how many ways there are to split it. Find the remainder when divided by $ 1,000,000,007 $.

• The example in the problem statement is the same.

• There are 5 ways to split that satisfy the following conditions:

Split MethodSum2+4+3+91824+3+9362+4+39452+43+95424+3963

Input Format

Input is given from the standard input in the following format:

$ N $ $ D $

• The first line contains the integer $ N $ to be split.
• The second line contains the upper limit of the sum $ D $.

Output Format

Output should follow the standard output format:

• Output the number of ways to split modulo $ 1,000,000,007 $ in one line.

Sample Input and Output

Sample Input #1

1355
50

Sample Output #1

3

Sample Input #2

2439
100

Sample Output #2

5

Sample Input #3

1225
20

Sample Output #3

2

Sample Input #4

123456
10000

Sample Output #4

29

Notes/Hints

Constraints

• $ 1≦N≦{10}^{100} $
• $ 1≦D≦100,000 $

Subtasks

Subtask $ 1 $ \[ $ 10 $ points \]

• The solution is at most $ 1 $ way.

Subtask $ 2 $ \[ $ 30 $ points \]

• $ 1≦N≦10,000,000,000 $ is satisfied.

Subtask $ 3 $ \[ $ 60 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分