← 返回题目列表

AtCoder · abc208_f

F. 累计金额

中文机器翻译题面 查看原题

分数: 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