/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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) で割った余りを出力せよ。
入力例 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
Score : 600 points
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