好编号

给定参数 $ N $、$ K $。一个编号 $ A $ 被称为好编号，当且仅当对于任意的 $ i \in \{ 1, 2, \cdots, N-1 \} $，均满足：$ \dfrac{A}{K^i} - \left\lfloor \dfrac{A}{K^i} \right\rfloor > \dfrac{A}{K^N} $。 求好编号的个数模 $ 10^9+7 $ 的值。

一行两个正整数 $N,K$。

一行，好编号个数模 $10 ^ 9 + 7$ 的值。

10 10

999989991

6 2

9

- 对于 $20\%$ 的数据，$K^N\leq 5\times 10 ^ 4$。 - 对于 $60\%$ 的数据， $N, K\leq 10 ^ 6$。 - 对于 $100\%$ 的数据，$1\leq N, K\leq 10 ^ 9$。