{"problem":{"name":"Modulo Sum of Increasing Sequences","description":{"content":"Find the number, modulo $998244353$, of non-decreasing sequences $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ consisting of integers between $0$ and $M$ (inclusive) that satisfy the following, for each $K=0","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc145_f"},"statements":[{"statement_type":"Markdown","content":"Find the number, modulo $998244353$, of non-decreasing sequences $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ consisting of integers between $0$ and $M$ (inclusive) that satisfy the following, for each $K=0,1,\\ldots,\\mathrm{MOD}-1$:\n\n*   the sum of the elements in $A$ is congruent to $K$ modulo $\\mathrm{MOD}$.\n\nWhat is a non-decreasing sequence? A sequence $B$ is non-decreasing if and only if $B_i \\leq B_{i+1}$ for every integer ($1 \\le i \\le |B| - 1$), where $|B|$ is the length of $B$.\n\n## Constraints\n\n*   $1 \\leq N ,M\\leq 10^6$\n*   $1\\leq \\mathrm{MOD}\\leq 500$\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$ $\\mathrm{MOD}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc145_f","tags":[],"sample_group":[["2 2 4","2 1 2 1\n\nThere are $6$ non-decreasing sequences of length $2$ consisting of integers between $0$ and $2$: $(0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2)$. Here, we have:\n\n*   $2$ sequences whose sums are congruent to $0$ modulo $4$: $(0,0),(2,2)$;\n    \n*   $1$ sequence whose sum is congruent to $1$ modulo $4$: $(0,1)$;\n    \n*   $2$ sequences whose sums are congruent to $2$ modulo $4$: $(0,2),(1,1)$;\n    \n*   $1$ sequence whose sum is congruent to $3$ modulo $4$: $(1,2)$."],["3 45 3","5776 5760 5760"],["1000000 1000000 6","340418986 783857865 191848859 783857865 340418986 635287738\n\nPrint the counts modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}