配点 : $600$ 点

問題文

非負整数 $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)$ で割った余りを出力せよ。

3 4 2

35

$K = 2$ の時、 $n \leq 3, m \leq 4$ における $f(n, m)$ の値は次のようになります。

0 1 2

0

1000000000000000000 30 123456

297085514