Hide

Problem J
Birthday Gift

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

Please log in to submit a solution to this problem

Log in