定义 $f_m(n)$ 表示将 $n$ 表示为若干 $m$ 的非负整数次幂的和的方案数。例如，当 $m=2$ 的时候，$f_2(4)=4$，一共有 $\{1,1,1,1\},\{1,1,2\},\{2,2\},\{4\}$ 这四种方案。
定义 $g_m^k(n)$ 为 $k$ 个 $f_m(n)$ 卷积起来的结果，即：
$$g_m^k(n)=\left\{\begin{matrix} f_m(n) & k=1 \\ \sum_{i=0}^n(g_m^{k-1}(i) \times f_m(n-i)) & otherwise \end{matrix}\right.$$
给定 $n,m,k$，请求出 $(\sum_{i=0}^n g_m^k(i))~mod~10^9+7$。
输入格式
一行三个整数 $n,m,k$。
输出格式
一个整数表示答案。
样例一
Input
16 4 3
Output
3692
样例二
Input
5 2 2
Output
56
限制与约定
Subtask1（8分）：$0 \leq n \leq 100, 2 \leq m \leq 10^{18}, 1 \leq k \leq 20$；
Subtask2（12分）：$0 \leq n \leq 1000, 2 \leq m \leq 10^{18}, 1 \leq k \leq 20$；
Subtask3（23分）：$0 \leq n \leq 10^5, 2 \leq m \leq 10^{18}, 1 \leq k \leq 20$；
Subtask4（27分）：$0 \leq n \leq 10^{18}, 2 \leq m \leq 10^{18}, k=1$；
Subtask5（10分）：$0 \leq n \leq 10^{18}, 10 < m \leq 10^{18}, 1 \leq k \leq 20$；
Subtask6（20分）：$0 \leq n \leq 10^{18}, 2 \leq m \leq 10^{18}, 1 \leq k \leq 20$。
时间限制：1s
空间限制：512MB
