One day, Kuong suddenly wondered, "How many expressions result in $N$?"

Kuong realized the sad fact that since appending +0, -0, etc., to an expression that results in $N$ still results in $N$, one could create infinitely many such expressions by repeating this process.

Therefore, Kuong added the constraint that the length of the expression must be $M$, but he could not find the answer. Let's solve this problem for him!

An expression is defined as follows:

• A term is a string of length $1$ or more consisting only of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 that does not start with 0. However, 0 is an exception and is a term even though it starts with 0.
• An expression is a string containing one or more terms, where each term is separated by + or -.

In other words, an expression is a string that satisfies the following regular expression:

• (([1-9][0-9]*|'0')[+-]))*([1-9][0-9]*|'0')

The first line contains $N$ and $M$ separated by a space, where $0 \le N \le 10^5$ and $1 \le M \le 11$.

Output the number of distinct expressions of length $M$ that result in $N$. Since there may be many such expressions, output the result modulo $10^9+7$.

Examples

Input 1

5 3

Output 1

11

Note

Example 1: There are $11$ expressions of length $3$ that result in $5$: 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 5-0, 6-1, 7-2, 8-3, and 9-4.

Input 2

123 3

Output 2

1

Note

Example 2: An expression may not contain + or -.

Input 3

100000 5

Output 3

0

Input 4

0 2

Output 4

0

Input 5

10 3

Output 5

9

Note

Example 5: An expression cannot start with + or -.