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$$$.
The only line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$1 \leq d \leq 6$$$).
Print the number of distinct numeric parts of displays modulo $$$10^9 + 7$$$.
1 1
55
4 2
7155947
6767 4
886886693
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).