{"problem":{"name":"Non-Adjacent Matching","description":{"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$. Here, a length-$N$ sequence $X=(X_1,X","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc156_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc156_e","tags":[],"sample_group":[["4 1 2","3\n\nThe following three sequences are good.\n\n*   $(0,0,0,0)$\n*   $(0,1,0,1)$\n*   $(1,0,1,0)$"],["10 0 0","1"],["314 159 26535","248950743\n\nPrint the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}