分数: 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,值 f(n, m) 为 n \leq 3, m \leq 4 如下。
| 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