Auction Bid Divisibility Count

iPig has organized an enormous auction in the Pig Kingdom. In the auction, N pigs stand in a row from left to right in non‐decreasing order of their bid amounts. Each pig holds a bid value between 1 and 9 (inclusive). The bids form an N-digit number when viewed from the stage. The highest bidding pig (or pigs, if there is a tie) will win iPig's secret code library. However, iPig is only interested in a challenging question: among all possible bid sequences that follow the rules, how many of the resulting N-digit numbers are divisible by P? Since this answer can be huge, output it modulo \(999911659\).

The bid sequence must satisfy the following:

• The number consists of exactly N digits.
• Each digit is an integer in the range \(\{1, 2, \dots, 9\}\).
• The digits are non-decreasing from left to right.

If we denote the bid sequence as \(d_1,d_2,\dots,d_N\), then it must satisfy \(d_1 \le d_2 \le \cdots \le d_N\) and the number \(X = d_1d_2\cdots d_N\) (in decimal) must be divisible by \(P\).

Note that a non-decreasing sequence can be uniquely represented by counts \(a_1, a_2, \dots, a_9\) where \(a_d\) is the number of pigs bidding \(d\) (with \(\sum_{d=1}^{9} a_d = N\)). Given these counts, the number can be constructed as follows: the leftmost \(a_1\) digits are all 1, the next \(a_2\) digits are all 2, and so on. When adding a block of \(a_d\) digits (all equal to \(d\)), if the current number is f, then the new number becomes:

[ \text{new} = f \times 10^{a_d} + d \times \frac{10^{a_d}-1}{9} \mod P. ]

Your task is to count the number of valid bid sequences so that the resulting N-digit number is divisible by P. Output the answer modulo \(999911659\).

inputFormat

The input consists of a single line containing two space-separated integers: N and P.

outputFormat

Output a single integer representing the number of valid bid sequences yielding an N-digit number divisible by P, taken modulo \(999911659\).

sample

1 1

9