Problem Description

Given parameters $N$ and $K$. A number $A$ is called a good number if and only if for every $i \in \{1, 2, \cdots, N-1\}$, the following holds: $\dfrac{A}{K^i} - \left\lfloor \dfrac{A}{K^i} \right\rfloor > \dfrac{A}{K^N}$.

Find the number of good numbers modulo $10^9+7$.

Input Format

One line with two positive integers $N, K$.

Output Format

One line, the number of good numbers modulo $10 ^ 9 + 7$.

10 10

999989991

6 2

9

Hint

• For $20\%$ of the testdata, $K^N \leq 5\times 10 ^ 4$.
• For $60\%$ of the testdata, $N, K \leq 10 ^ 6$.
• For $100\%$ of the testdata, $1 \leq N, K \leq 10 ^ 9$.

Translated by ChatGPT 5