P8825 [Chuanzhi Cup #3 Preliminary] Luck

YYH Land (Yoauld, Youthful & Happy Land) is a magical kingdom located in the Azure Immortal Wilds, where people live a free and happy life.

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$.

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

One line with one integer, the answer.

**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