9412: ABC208 —— F - Cumulative Sum
[Creator : ]
Description
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)$.
$\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)$.
Input
Input is given from Standard Input in the following format:
```
$N$ $M$ $K$
```
```
$N$ $M$ $K$
```
Output
Print $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.
- $0 \leq M \leq 30$
- $1 \leq K \leq 2.5 \times 10^6$
- All values in input are integers.
Sample 1 Input
3 4 2
Sample 1 Output
35
When K=2, the values f(n,m) for n≤3,m≤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 |
Sample 2 Input
0 1 2
Sample 2 Output
0
Sample 3 Input
1000000000000000000 30 123456
Sample 3 Output
297085514