It’s your Venusian friend’s birthday. You don’t remember
their exact age, but you are sure it had to be no more than
$10^{18}$ years. You will
give them a decimal number (without leading zeros) for their
birthday. You want the number of digits to be equal to their
age. To make the number more interesting you will ensure that
no adjacent pairs of digits will be identical.
Their exact day of birth is represented as an integer in the
range $0$ to $224$ (since Venus has $225$ days in a year). To make their
gift more personal you want the given number to have the same
remainder as their birthday when divided by $225$.
There are potentially a lot of possible gifts that you could
give. You may decide to give more than one gift. Determine the
number of possible gifts modulo $10^9+7$.
Input
The single line of input contains two space separated
integers $a$ ($1 \le a \le 10^{18}$) and
$b$ ($0 \le b < 225$), where
$a$ is the age of your
friend and $b$ is the
birthdate of your friend.
Output
Output a single integer, which is the number of interesting
personalized numbers you could give. Since this number may be
quite large, output it modulo $10^9+7$.
| Sample Input 1 |
Sample Output 1 |
12345 200
|
323756255
|
| Sample Input 2 |
Sample Output 2 |
100 87
|
896364174
|
| Sample Input 3 |
Sample Output 3 |
100 35
|
785970618
|
| Sample Input 4 |
Sample Output 4 |
5000 5
|
176058968
|
| Sample Input 5 |
Sample Output 5 |
888888 88
|
906317283
|
| Sample Input 6 |
Sample Output 6 |
9999999 99
|
133442170
|
| Sample Input 7 |
Sample Output 7 |
101010101010 127
|
893501348
|
