Problem Statement

For non-negative integers $n$ and $m$, let us define the function $f(n, m)$ as follows, using a positive integer $K$.

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

Given $N$, $M$, and $K$, find $f(N, M)$ modulo $(10 ^ 9 + 7)$.

Constraints

• $0 \\leq N \\leq 10^{18}$
• $0 \\leq M \\leq 30$
• $1 \\leq K \\leq 2.5 \\times 10^6$
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

$N$ $M$ $K$

Output

Print $f(N, M)$ modulo $(10 ^ 9 + 7)$.

---

Sample Input 1

3 4 2

Sample Output 1

35

When $K = 2$, the values $f(n, m)$ for $n \\leq 3, m \\leq 4$ are as follows.

$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$

---

Sample Input 2

0 1 2

Sample Output 2

0

---

Sample Input 3

1000000000000000000 30 123456

Sample Output 3

297085514