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$ 的余数。

样例 1

输入

3 4 2

输出

35

样例 2

输入

0 1 2

输出

0

样例 3

输入

1000000000000000000 30 123456

输出

297085514

说明/提示

限制条件

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