AT_abc208_f [ABC208F] Cumulative Sum

对于非负整数 $n,\ m$，定义函数 $f(n,\ m)$，使用正整数 $K$，如下所示： $$ f(n,\ m) = \begin{cases} 0 & (n = 0) \\ n^K & (n > 0,\ m = 0) \\ f(n-1,\ m) + f(n,\ m-1) & (n > 0,\ m > 0) \end{cases} $$ 给定 $N,\ M,\ K$，请计算 $f(N,\ M)$ 除以 $10^9 + 7$ 的余数。

输入以如下格式从标准输入读入： > $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$ - 输入均为整数。 ## 样例解释 1 当 $K = 2$ 时，$n \leq 3,\ m \leq 4$ 时 $f(n,\ m)$ 的值如下表所示： \[ \begin{array}{c|ccccc} & m=0 & m=1 & m=2 & m=3 & m=4 \\ \hline 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 \\ \end{array} \] 由 ChatGPT 4.1 翻译