AtCoder Beginner Contest 208
翻译中…
Problem Statement
翻译中…
For non-negative integers $n$ and $m$, let us define the function $f(n, m)$ as follows, using a positive integer $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}$
翻译中…
Given $N$, $M$, and $K$, find $f(N, M)$ modulo $(10 ^ 9 + 7)$.
翻译中…
Constraints
翻译中…
$0 \leq N \leq 10^{18}$$0 \leq M \leq 30$$1 \leq K \leq 2.5 \times 10^6$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N M K翻译中…
Output
翻译中…
Print $f(N, M)$ modulo $(10 ^ 9 + 7)$.
翻译中…
样例
Input #1
3 4 2
Output #1
35
When $K = 2$, the values $f(n, m)$ for $n \leq 3, m \leq 4$ are as follows.
| | $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$ |
Input #2
0 1 2
Output #2
0
Input #3
1000000000000000000 30 123456
Output #3
297085514
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。