{"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(n-1, m) + f(n, m-1) & (n \\gt 0, m \\gt 0) \\end{cases}$\nGiven $N$, $M$, and $K$, find $f(N, M)$ modulo $(10 ^ 9 + 7)$.\n\n## Constraints\n\n*   $0 \\leq N \\leq 10^{18}$\n*   $0 \\leq M \\leq 30$\n*   $1 \\leq K \\leq 2.5 \\times 10^6$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc208_f","tags":[],"sample_group":[["3 4 2","35\n\nWhen $K = 2$, the values $f(n, m)$ for $n \\leq 3, m \\leq 4$ are as follows.\n\n$m = 0$\n\n$m = 1$\n\n$m = 2$\n\n$m = 3$\n\n$m = 4$\n\n$n = 0$\n\n$0$\n\n$0$\n\n$0$\n\n$0$\n\n$0$\n\n$n = 1$\n\n$1$\n\n$1$\n\n$1$\n\n$1$\n\n$1$\n\n$n = 2$\n\n$4$\n\n$5$\n\n$6$\n\n$7$\n\n$8$\n\n$n = 3$\n\n$9$\n\n$14$\n\n$20$\n\n$27$\n\n$35$"],["0 1 2","0"],["1000000000000000000 30 123456","297085514"]],"created_at":"2026-03-03 11:01:13"}}