题目描述

非負整数 $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)$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

输出格式

$f(N,\ M)$ を $(10\ ^\ 9\ +\ 7)$ で割った余りを出力せよ。

题目大意

给定非负整数 $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} $

对 $\left(10^9+7\right)$ 取模后的值。

3 4 2

35

0 1 2

0

1000000000000000000 30 123456

297085514

提示

制約

• $0\ \leq\ N\ \leq\ 10^{18}$
• $0\ \leq\ M\ \leq\ 30$
• $1\ \leq\ K\ \leq\ 2.5\ \times\ 10^6$
• 入力は全て整数である。

Sample Explanation 1

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