{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$S_1$ $\\ldots$ $S_N$"},{"iden":"sample input 1","content":"4 2\n1 0 0 1"},{"iden":"sample output 1","content":"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)$"},{"iden":"sample input 2","content":"10 1000000000\n0 0 1 0 0 0 1 0 1 0"},{"iden":"sample output 2","content":"587954969\n\nBe sure to find the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}