{"problem":{"name":"Prefix Mex Sequence","description":{"content":"For a sequence $X$ composed of a finite number of non-negative integers, we define $\\mathrm{mex}(X)$ as the smallest non-negative integer not in $X$. For example, $\\mathrm{mex}((0,0, 1,3)) = 2, \\mathr","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc170_c"},"statements":[{"statement_type":"Markdown","content":"For a sequence $X$ composed of a finite number of non-negative integers, we define $\\mathrm{mex}(X)$ as the smallest non-negative integer not in $X$. For example, $\\mathrm{mex}((0,0, 1,3)) = 2, \\mathrm{mex}((1)) = 0, \\mathrm{mex}(()) = 0$.\nYou are given a sequence $S=(S_1,\\ldots,S_N)$ of length $N$ where each element is $0$ or $1$.\nFind the number, modulo $998244353$, of sequences $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ consisting of integers between $0$ and $M$, inclusive, that satisfy the following condition:\n\n*   For each $i (1\\leq i\\leq N)$, $A_i = \\mathrm{mex}((A_1,A_2,\\ldots,A_{i-1}))$ if $S_i=1$, and $A_i \\neq \\mathrm{mex}((A_1,A_2,\\ldots,A_{i-1}))$ if $S_i=0$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $0 \\leq M \\leq 10^9$\n*   $S_i$ is $0$ or $1$.\n*   All input numbers are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$S_1$ $\\ldots$ $S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc170_c","tags":[],"sample_group":[["4 2\n1 0 0 1","4\n\nThe following four sequences satisfy the conditions:\n\n*   $(0,0,0,1)$\n*   $(0,0,2,1)$\n*   $(0,2,0,1)$\n*   $(0,2,2,1)$"],["10 1000000000\n0 0 1 0 0 0 1 0 1 0","587954969\n\nBe sure to find the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}