F - Cumulative Sum
F - 累積和
得分：$600$ 分
问题描述
对于非负整数 $n$ 和 $m$，我们使用正整数 $K$ 定义函数 $f(n, m)$ 如下。
$\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$
- 输入中的所有值都是整数。
输入
输入数据从标准输入中以以下格式给出：
输出
打印值为 $f(N, M)$ 在模 $(10 ^ 9 + 7)$ 下的结果。
3 4 2
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$ |
0 1 2
0
1000000000000000000 30 123456
297085514