Problem Description

Find the number of positive integers less than or equal to $N$ such that the sum of their digits in base 10 is a multiple of $D$, modulo 1,000,000,007.

Input Format

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

$D$

$N$

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

3
100

Sample Output #1

33

Sample Input #2

7
123456789012345678901234567890

Sample Output #2

468357804

Notes/Hints

Constraints

• $1 \le N \le 10^{10000}$
• $1 \le D \le 100$

Sample Explanation 1

The 33 multiples of 3 between 1 and 100 satisfy the condition.

见题面 Input 部分

见题面 Output 部分