Cumulative Sum

AtCoder

IDabc208_f

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

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

Input #3

1000000000000000000 30 123456

Output #3

297085514

API Response (JSON)

{
  "problem": {
    "name": "Cumulative Sum",
    "description": {
      "content": "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(",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc208_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For non-negative integers $n$ and $m$, let us define the function $f(n, m)$ as follows, using a positive integer $K$.\n$\\displaystyle f(n, m) = \\begin{cases} 0 & (n = 0) \\\\ n^K & (n \\gt 0, m = 0) \\\\ f(...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments