Little Z is playing a game called "Gold Miner". The world of the game is a two-dimensional coordinate system. The range of coordinates on both the X-axis and Y-axis is $1..N$. Initially, there is one piece of gold at every integer coordinate point, for a total of $N \times N$ pieces.
A gust of wind blows, and the positions of the gold pieces change. Careful Little Z discovers that a piece of gold initially at coordinate $(i, j)$ moves to coordinate $(f(i), f(j))$. Here, $f(x)$ represents the product of the digits of $x$. For example, $f(99)=81$, $f(12)=2$, and $f(10)=0$. If the coordinate after the change is not within the range $1..N$, we consider that piece of gold to have been removed from the game. It can also be observed that in the game state after the change, some coordinates may have more than one piece of gold, while others may have none. After this change, the positions and quantities of the gold will not change again, and the player can begin collecting.
Little Z is lazy and intends to perform only $K$ collections. Each collection allows the player to obtain all the gold at a specific coordinate, and after collection, the number of gold pieces at that coordinate becomes 0.
Now, Little Z wants to know, for the game state after the change, given that the number of collections is $K$, what is the maximum number of gold pieces that can be collected?
The answer may be very large, and Little Z wishes to obtain the answer modulo $1000000007$ ($10^9+7$).
Input
A single line containing two positive integers $N$ and $K$.
Output
A single integer representing the maximum number of gold pieces that can be collected.
Examples
Input 1
12 5
Output 1
18
Note
The number of gold pieces at each coordinate after the change is as follows:
| Row/Col | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 4 | 4 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 |
| 2 | 4 | 4 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 |
| 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 4 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 5 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 6 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 7 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 8 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 9 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
One can collect the gold at (1, 1), (1, 2), (2, 1), (2, 2), (3, 1) in sequence, for a total of 18 pieces.
Constraints
| Test Case ID | N | K |
|---|---|---|
| 1, 2 | $N \le 1000$ | $K \le 100000$ |
| 3, 4 | $N \le 1000000$ | $K \le 100000$ |
| 5, 6 | $N = 10^{12}$ | $K \le 100000$ |
| 7, 8 | $N \le 10^{12}$ | $K = 1$ |
| 9, 10 | $N \le 10^{12}$ | $K \le 100000$ |
For 100% of the test data: $K \le N^2$.