AT_abc246_h [ABC246Ex] 01? Queries

给定一个只包含 `0`、`1`、`?` 的长度为 $N$ 的字符串 $S$。 此外，给定 $Q$ 个查询 $(x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q)$。 其中，对于 $i = 1, 2, \ldots, Q$，$x_i$ 是满足 $1 \leq x_i \leq N$ 的整数，$c_i$ 是 `0`、`1`、`?` 中的任意一个字符。 请依次对每个查询 $(x_i, c_i)$ 执行以下操作： 1. 首先，将 $S$ 的第 $x_i$ 个字符（从前往后数）修改为 $c_i$。 2. 然后，输出将 $S$ 中所有的 `?` 独立地替换为 `0` 或 `1` 后，所有可能得到的字符串的（不一定连续的）子序列中，所有可能出现的非空字符串的个数，结果对 $998244353$ 取模。

输入按以下格式从标准输入给出。 > $N$ $Q$ > $S$ > $x_1$ $c_1$ > $x_2$ $c_2$ > $\vdots$ > $x_Q$ $c_Q$

输出 $Q$ 行。对于 $i = 1, 2, \ldots, Q$，第 $i$ 行输出第 $i$ 个查询 $(x_i, c_i)$ 的答案（即上述操作 2 中的字符串个数对 $998244353$ 取模的结果）。

## 限制条件 - $1 \leq N, Q \leq 10^5$ - $N, Q$ 为整数 - $S$ 是只包含 `0`、`1`、`?` 的长度为 $N$ 的字符串 - $1 \leq x_i \leq N$ - $c_i$ 是 `0`、`1`、`?` 中的任意一个字符 ## 样例解释 1 - 第 1 个查询后，$S = 110$。作为 $S = 110$ 的子序列可能出现的字符串有：`0`、`1`、`10`、`11`、`110`，共 $5$ 个。因此，第 1 个查询的答案为 $5$。 - 第 2 个查询后，$S = 1?0$。将 `?` 替换为 `0` 或 `1` 后得到的字符串为 `100` 和 `110`，它们的所有子序列可能出现的字符串有：`0`、`1`、`00`、`10`、`11`、`100`、`110`，共 $7$ 个。因此，第 2 个查询的答案为 $7$。 - 第 3 个查询后，$S = 1??$。将两个 `?` 替换为 `0` 或 `1` 后得到的字符串为 `100`、`101`、`110`、`111`，它们的所有子序列可能出现的字符串有：`0`、`1`、`00`、`01`、`10`、`11`、`100`、`101`、`110`、`111`，共 $10$ 个。因此，第 3 个查询的答案为 $10$。 ## 样例解释 2 请注意，答案需要对 $998244353$ 取模。 由 ChatGPT 4.1 翻译