{"raw_statement":[{"iden":"problem statement","content":"Find the number, modulo $998244353$, of sequences of $N$ non-negative integers $A=(A_1,A_2,\\dots,A_N)$ totaling $M$ that satisfy the following condition.\n\n*   It is possible to make all elements of $A$ equal $0$ by repeatedly choosing one of the following operations and performing it.\n    *   Choose an integer $i$ such that $1 \\le i \\le N$ and decrease $A_i$ by $K$.\n    *   Choose an integer $i$ such that $1 \\le i \\le N-K+1$ and decrease each of $A_i,A_{i+1},\\dots,A_{i+K-1}$ by $1$."},{"iden":"constraints","content":"*   $1 \\le K \\le N \\le 2000$\n*   $1 \\le M \\le 10^{18}$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $K$"},{"iden":"sample input 1","content":"3 2 2"},{"iden":"sample output 1","content":"5\n\nThe following five sequences satisfy the requirements.\n\n*   $(1,1,0)$\n*   $(0,1,1)$\n*   $(2,0,0)$\n*   $(0,2,0)$\n*   $(0,0,2)$\n\nFor instance, if $A=(0,1,1)$, you can do the following to make all elements of $A$ equal $0$.\n\n*   Perform the second operation. Choose $i = 2$ to decrease each of $A_2$ and $A_3$ by $1$, making $A=(0,0,0)$."},{"iden":"sample input 2","content":"100 998244353 100"},{"iden":"sample output 2","content":"0\n\nThere may be no sequence that satisfies the requirements."},{"iden":"sample input 3","content":"2000 545782618661124208 533"},{"iden":"sample output 3","content":"908877889"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}