{"raw_statement":[{"iden":"problem statement","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)$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $K$"},{"iden":"sample input 1","content":"3 4 2"},{"iden":"sample output 1","content":"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$"},{"iden":"sample input 2","content":"0 1 2"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"1000000000000000000 30 123456"},{"iden":"sample output 3","content":"297085514"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}