问题描述

给定一个长度为 $N$ 的字符串 $S$，由 0、1 和 ? 组成。

还给出了 $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 或 ? 中的一个。

按照顺序对于 $i = 1, 2, \ldots, Q$，对查询 $(x_i, c_i)$ 进行以下步骤。

1. 首先，将 $S$ 起始处的第 $x_i$ 个字符改为 $c_i$。
2. 然后，计算在将 $S$ 中的每个 ? 替换为 0 或 1 后，可以作为 $S$ 的（不一定连续）子序列获得的非空字符串数量，对 $998244353$ 取模。

约束条件

• $1 \leq N, Q \leq 10^5$
• $N$ 和 $Q$ 是整数。
• $S$ 是一个长度为 $N$ 的字符串，由 0、1 和 ? 组成。
• $1 \leq x_i \leq N$
• $c_i$ 是字符 0、1 或 ? 中的一个。

输入

输入以以下格式从标准输入获得：

$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

3 3
100
2 1
2 ?
3 ?

示例输出 1

5
7
10

• 第 1 个查询将 $S$ 改为 110。可以从 $S =$ 110 获得五个字符串作为其子序列：0、1、10、11、110。因此，第 1 个查询的答案是 $5$。

• 第 2 个查询将 $S$ 改为 1?0。可以从 $S =$ 1?0 中的 ? 获得两个字符串：100 和 110。可以从这两个字符串的子序列中获得七个字符串：0、1、00、10、11、100、110。因此，第 2 个查询的答案是 $7$。

• 第 3 个查询将 $S$ 改为 1??。可以从 $S =$ 1?? 中的 ? 获得四个字符串：100、101、110、111。可以从这四个字符串的子序列中获得十个字符串：0、1、00、01、10、11、100、101、110、111。因此，第 3 个查询的答案是 $10$。

示例输入 2

40 10
011?0??001??10?0??0?0?1?11?1?00?11??0?01
5 0
2 ?
30 ?
7 1
11 1
3 1
25 1
40 0
12 1
18 1

示例输出 2

746884092
532460539
299568633
541985786
217532539
217532539
217532539
573323772
483176957
236273405

请务必对 $998244353$ 进行取模操作。