题目描述

对于非负整数 $n$ 和 $m$，我们用一个正整数 $K$ 定义函数 $f(n, m)$ 如下。

$\\displaystyle f(n, m) = \\begin{cases} 0 & (n = 0) \\\\ n^K & (n > 0, m = 0) \\\\ f(n-1, m) + f(n, m-1) & (n > 0, m > 0) \\end{cases}$

给定 $N$、$M$ 和 $K$，求 $f(N, M)$ 对 $(10 ^ 9 + 7)$ 取模的结果。

约束条件

• $0 \leq N \leq 10^{18}$
• $0 \leq M \leq 30$
• $1 \leq K \leq 2.5 \times 10^6$
• 输入中的所有值都是整数。

---

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $K$

输出

输出 $f(N, M)$ 对 $(10 ^ 9 + 7)$ 取模的结果。

---

示例输入 1

3 4 2

示例输出 1

35

当 $K = 2$ 时，$n \leq 3, m \leq 4$ 的值 $f(n, m)$ 如下所示。

$m = 0$

$m = 1$

$m = 2$

$m = 3$

$m = 4$

$n = 0$

$0$

$0$

$0$

$0$

$0$

$n = 1$

$1$

$1$

$1$

$1$

$1$

$n = 2$

$4$

$5$

$6$

$7$

$8$

$n = 3$

$9$

$14$

$20$

$27$

$35$

---

示例输入 2

0 1 2

示例输出 2

0

---

示例输入 3

1000000000000000000 30 123456

示例输出 3

297085514