問題文

非負整数 $n, m$ に対して関数 $f(n, m)$ を正の整数 $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}$

$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