题目描述

给定参数 $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$。