设 $m$ 为一个固定的整数，满足 $m \ge 2$。对于正整数 $n$，令 $b_m(n)$ 表示将 $n$ 写成 $m$ 的幂之和的方法数，其中允许使用非负整数指数，允许重复，且不考虑加数的顺序。我们同时设定 $b_m(0) = 1$（存在一种空和）。

例如，$\{b_2(n)\}$ 的前 10 项为 $\{1, 1, 2, 2, 4, 4, 6, 6, 10, 10\}$，$\{b_3(n)\}$ 的前 10 项为 $\{1, 1, 1, 2, 2, 2, 3, 3, 3, 5\}$。

令 $c_m^k(n)$ 为 $b_m(n)$ 的 $k$ 次卷积幂，其定义如下：

$$c_m^k(n) = \begin{cases} b_m(n), & k = 1 \\ \sum_{i=0}^n b_m(i) \cdot c_m^{k-1}(n - i), & k \ge 2 \end{cases}$$

给定 $n, m$ 和 $k$，Bobo 想要计算以下值：

$$f(n) = \left( \sum_{i=0}^n c_m^k(i) \right) \pmod{10^9 + 7}$$

输入格式

第一行包含三个整数 $n, m$ 和 $k$ ($0 \le n \le 10^{18}, 2 \le m \le 10^{18}, 1 \le k \le 10$)。

输出格式

输出一个整数，表示 $f(n)$ 的值。

样例

样例输入 1

0 2 1

样例输出 1

1

样例输入 2

10 2 3

样例输出 2

2700

样例输入 3

100 2 10

样例输出 3

490796617