Description

Harlan Sweety is a well-known lead-loaded dice enthusiast in YYH Land. One day, he ran into the following problem:

You have a $6$-faced die, labeled $1,2,3,4,5,6$, and each face has an equal probability of landing face up.

Now Harlan wants to know: if he rolls the die $n$ times and writes the results in order on paper to form a number (for example, if Harlan rolls $3$ times and gets $3,2,5$, then the final number is $325$), how many possible outcomes make this number a multiple of $k$, where $k$ is a given number.

Since the number of such outcomes may be very large, output the result modulo $10^9+7$.

Input Format

One line with two integers $n,k$, as described above.

Output Format

One line with one integer, the answer.

2 11

6

Hint

Sample Explanation

Among the $36$ possible outcomes of rolling the die twice, only $("11","22","33","44","55","66")$ meet the condition. Therefore, the answer is $6$.

Constraints

For $40\%$ of the testdata, $n$ is $1,2,3,4$, respectively.
For another $30\%$ of the testdata, $1 \leq k \leq 3$.
For $100\%$ of the testdata, $1 \leq n \leq 10$ and $1 \leq k \leq 1000$.

Translated by ChatGPT 5