{"raw_statement":[{"iden":"problem statement","content":"Find the number, modulo $998244353$, of **good sequences** of length $N$ whose elements are integers between $0$ and $M$, inclusive, and whose sum is at most $K$.\nHere, a length-$N$ sequence $X=(X_1,X_2,\\ldots,X_N)$ is said to be good if and only if there is a graph $G$ that satisfies all of the following conditions.\n\n*   $G$ is a graph with $N$ vertices numbered $1$ to $N$ without self-loops. (It may have multi-edges.)\n*   For each $i\\ (1\\leq i \\leq N)$, the degree of vertex $i$ is $X_i$.\n*   For each $i\\ (1\\leq i \\leq N)$, no edge connects vertex $i$ and vertex $i+1$. Here, vertex $N+1$ means vertex $1$."},{"iden":"constraints","content":"*   $4 \\leq N \\leq 3000$\n*   $0 \\leq M \\leq 3000$\n*   $0\\leq K \\leq NM$\n*   All numbers in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $K$"},{"iden":"sample input 1","content":"4 1 2"},{"iden":"sample output 1","content":"3\n\nThe following three sequences are good.\n\n*   $(0,0,0,0)$\n*   $(0,1,0,1)$\n*   $(1,0,1,0)$"},{"iden":"sample input 2","content":"10 0 0"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"314 159 26535"},{"iden":"sample output 3","content":"248950743\n\nPrint the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}