{"problem":{"name":"Ex - 01? Queries","description":{"content":"You are given a string $S$ of length $N$ consisting of `0`, `1`, and `?`. You are also given $Q$ queries $(x_1, c_1), (x_2, c_2), \\ldots, (x_Q, c_Q)$.   For each $i = 1, 2, \\ldots, Q$, $x_i$ is an int","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc246_h"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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 `?`.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc246_h","tags":[],"sample_group":[["3 3\n100\n2 1\n2 ?\n3 ?","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$."],["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","746884092\n532460539\n299568633\n541985786\n217532539\n217532539\n217532539\n573323772\n483176957\n236273405\n\nBe sure to print the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:13"}}