Score : $600$ points

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)$.

3 4 2

35

When $K = 2$, the values $f(n, m)$ for $n \leq 3, m \leq 4$ are as follows.

0 1 2

0

1000000000000000000 30 123456

297085514