D. Digital Display
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In Minsk, a bus stop is often equipped with a display showing how soon buses on certain routes will arrive:

The numeric part of the display consists of $$$n$$$ rows and two columns. At any moment in time, the display shows upcoming buses of $$$k$$$ ($$$0 \leq k \leq n$$$) different routes. In such a case, the first $$$k$$$ rows are filled, and the remaining $$$n - k$$$ rows are completely empty.

The $$$i$$$-th filled row contains a positive integer $$$a_i$$$ in the first column and may contain a positive integer $$$b_i$$$ in the second column (otherwise, that cell is empty). It means that the time until the next bus of the described route is $$$a_i$$$ minutes, and if $$$b_i$$$ is present, the time until the subsequent bus is $$$b_i$$$ minutes (otherwise, there is no subsequent bus). Of course, if $$$b_i$$$ is present, then $$$b_i \geq a_i$$$.

The routes are placed in non-decreasing order of next bus waiting time, that is, $$$a_{i + 1} \geq a_i$$$ for all suitable $$$i$$$. Note that the numbers in the second column are not necessarily sorted, nor are they necessarily present.

As columns have a fixed width of $$$d$$$ digits, all present numbers have to be between $$$1$$$ and $$$10^d - 1$$$, inclusive.

Your task, however, does not require knowing the complicated schedule of the transport system. Just find the number of distinct numeric parts of displays. Since the number can be large, find it modulo $$$10^9 + 7$$$.

Input

The only line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$1 \leq d \leq 6$$$).

Output

Print the number of distinct numeric parts of displays modulo $$$10^9 + 7$$$.

Examples
Input
1 1
Output
55
Input
4 2
Output
7155947
Input
6767 4
Output
886886693
Note

In the first example, there exist $$$1$$$ empty table, $$$9$$$ tables with one filled cell, and $$$45$$$ tables with two filled cells. Thus, the answer is $$$55$$$.

The illustration in the problem shows an example of a correct display (left) and an example of an incorrect display (right).