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 翻译