Assume that $*s*_{*k*}(*n*)$ equals the sum of digits of number $*n*$ in the $*k*$-based notation. For example, $*s*_{2}(5) = *s*_{2}(101_{2}) = 1 + 0 + 1 = 2$, $*s*_{3}(14) = *s*_{3}(112_{3}) = 1 + 1 + 2 = 4$.

The sequence of integers $*a*_{0}, ..., *a*_{*n* - 1}$ is defined as . Your task is to calculate the number of distinct subsequences of sequence $*a*_{0}, ..., *a*_{*n* - 1}$. Calculate the answer modulo $10^{9} + 7$.

Sequence $*a*_{1}, ..., *a*_{*k*}$ is called to be a subsequence of sequence $*b*_{1}, ..., *b*_{*l*}$, if there is a sequence of indices $1 ≤ *i*_{1} < ... < *i*_{*k*} ≤ *l*$, such that $*a*_{1} = *b*_{*i*_{1}}$, ..., $*a*_{*k*} = *b*_{*i*_{*k*}}$. In particular, an empty sequence (i.e. the sequence consisting of zero elements) is a subsequence of any sequence.

Input

The first line contains two space-separated numbers $*n*$ and $*k*$ ($1 ≤ *n* ≤ 10^{18}$, $2 ≤ *k* ≤ 30$).

Output

In a single line print the answer to the problem modulo $10^{9} + 7$.

Note

In the first sample the sequence $*a*_{*i*}$ looks as follows: $(0, 1, 1, 0)$. All the possible subsequences are:

$(), (0), (0, 0), (0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 1, 0), (1), (1, 0), (1, 1), (1, 1, 0).$

In the second sample the sequence $*a*_{*i*}$ looks as follows: $(0, 1, 2, 3, 4, 5, 6)$. The subsequences of this sequence are exactly all increasing sequences formed from numbers from 0 to 6. It is easy to see that there are $2^{7} = 128$ such sequences.