Dice Divisibility

Harlan Swithy is a famous dice enthusiast in YYH Land. One day, he encountered the following problem:

You are given a fair 6-faced dice with faces numbered \(1,2,3,4,5,6\) (each face has an equal probability). Harlan throws the dice \(n\) times and writes down the results in order to form a number. For example, if he throws the dice three times and gets \(3,2,5\), the resulting number is \(325\).

Your task is to determine how many outcomes produce a number that is a multiple of a given integer \(k\). Since the answer can be very large, output the result modulo \(10^9+7\).

The recurrence to compute the number of favorable sequences is given by

\[ \text{dp}[i+1][r'] = \sum_{d=1}^{6} \text{dp}[i][r], \quad \text{where} \quad r' = (10\cdot r + d) \mod k, \]

with the initial condition \(\text{dp}[0][0]=1\) and \(\text{dp}[0][r]=0\) for \(r\neq 0\). The final answer is \(\text{dp}[n][0]\).

inputFormat

The input consists of a single line containing two integers (n) and (k) separated by a space, where (n) is the number of dice throws and (k) is the divisor.

outputFormat

Output a single integer which is the number of outcomes that yield a number divisible by (k), taken modulo (10^9+7).

sample

1 2

3