As iPig's proficiency in the P++ language has improved, he has developed his own complete code library. The piglets in the Pig Kingdom who want to participate in the POI are scrambling to ask iPig for his code library. iPig does not want to give the code library to all the piglets who want it; he only wants to give it to a portion of the piglets who are both close friends and willing to pay. Therefore, he decided to hold a super-large auction.
At the auction, all $N$ piglets will stand in a row in front of iPig, ordered from lowest to highest affinity with iPig, from left to right. Each piglet has 9 pig coins. Starting from the leftmost piglet, each piglet holds up a sign with the number of pig coins (an integer from 1 to 9) they are willing to pay for the code library. Everyone knows that if they pay less than the piglet to their left, they will certainly not get the coveted code library. Therefore, starting from the second piglet, each piglet must bid an amount greater than or equal to the bid of the piglet to their left. The piglet(s) who bid the most will receive iPig's code library and move toward their dream of being admitted to PKU (Pig Kingdom University).
iPig is very satisfied with this idea. On his way to the venue, he imagined the scenarios that might occur at the auction, such as how many different bidding situations there would be. However, these questions were too simple, and iPig was no longer interested in them; he wanted to study more difficult problems. iPig discovered that if he looked down from the stage, the signs held by all the piglets from left to right would form an $N$-digit integer. The problem he now wants to challenge is: among all possible integers that can be formed, how many are exactly divisible by $P$? Since the answer is very large, he only wants to know the answer modulo $999911659$.
Input
The input consists of a single line containing two integers $N$ ($1 \le N \le 10^{18}$) and $P$ ($1 \le P \le 500$), separated by a space.
Output
The output consists of a single line containing one integer, representing the answer modulo $999911659$.
Examples
Input 1
2 3
Output 1
15
Note
The possible combinations are: 12, 15, 18, 24, 27, 33, 36, 39, 45, 48, 57, 66, 69, 78, 99, for a total of 15.
Constraints
| Test Case | $N$ | $P$ | Test Case | $N$ | $P$ |
|---|---|---|---|---|---|
| 1 | $\le 1000$ | $\le 500$ | 6 | $\le 10^6$ | $\le 500$ |
| 2 | $\le 10^{18}$ | $5$ | 7 | $\le 10^{18}$ | $\le 120$ |
| 3 | $\le 10^{18}$ | $\le 10$ | 8 | $\le 10^{18}$ | $\le 500$ |
| 4 | $\le 10^{18}$ | $\le 10$ | 9 | $\le 10^{18}$ | $\le 500$ |
| 5 | $\le 10^{18}$ | $25$ | 10 | $\le 10^{18}$ | $\le 500$ |