P5134 Good Numbers

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

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

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

- 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