{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ of length $N$ consisting of `0`, `1`, and `?`.\nYou are also given $Q$ queries $(x_1, c_1), (x_2, c_2), \\ldots, (x_Q, c_Q)$.  \nFor each $i = 1, 2, \\ldots, Q$, $x_i$ is an integer satisfying $1 \\leq x_i \\leq N$ and $c_i$ is one of the characters `0` , `1`, and `?`.\nFor $i = 1, 2, \\ldots, Q$ in this order, do the following process for the query $(x_i, c_i)$.\n\n1.  First, change the $x_i$\\-th character from the beginning of $S$ to $c_i$.\n2.  Then, print the number of non-empty strings, modulo $998244353$, that can be obtained as a (not necessarily contiguous) subsequence of $S$ after replacing each occurrence of `?` in $S$ with `0` or `1` independently."},{"iden":"constraints","content":"*   $1 \\leq N, Q \\leq 10^5$\n*   $N$ and $Q$ are integers.\n*   $S$ is a string of length $N$ consisting of `0`, `1`, and `?`.\n*   $1 \\leq x_i \\leq N$\n*   $c_i$ is one of the characters `0` , `1`, and `?`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$\n$S$\n$x_1$ $c_1$\n$x_2$ $c_2$\n$\\vdots$\n$x_Q$ $c_Q$"},{"iden":"sample input 1","content":"3 3\n100\n2 1\n2 ?\n3 ?"},{"iden":"sample output 1","content":"5\n7\n10\n\n*   The $1$\\-st query starts by changing $S$ to `110`. Five strings can be obtained as a subsequence of $S = $ `110`: `0`, `1`, `10`, `11`, `110`. Thus, the $1$\\-st query should be answered by $5$.\n    \n*   The $2$\\-nd query starts by changing $S$ to `1?0`. Two strings can be obtained by the `?` in $S = $ `1?0`: `100` and `110`. Seven strings can be obtained as a subsequence of one of these strings: `0`, `1`, `00`, `10`, `11`, `100`, `110`. Thus, the $2$\\-nd query should be answered by $7$.\n    \n*   The $3$\\-rd query starts by changing $S$ to `1??`. Four strings can be obtained by the `?`'s in $S = $ `1??`: `100`, `101`, `110`, `111`. Ten strings can be obtained as a subsequence of one of these strings: `0`, `1`, `00`, `01`, `10`, `11`, `100`, `101`, `110`, `111`. Thus, the $3$\\-rd query should be answered by $10$."},{"iden":"sample input 2","content":"40 10\n011?0??001??10?0??0?0?1?11?1?00?11??0?01\n5 0\n2 ?\n30 ?\n7 1\n11 1\n3 1\n25 1\n40 0\n12 1\n18 1"},{"iden":"sample output 2","content":"746884092\n532460539\n299568633\n541985786\n217532539\n217532539\n217532539\n573323772\n483176957\n236273405\n\nBe sure to print the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}