01? 查询

题目描述

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

还给定 $Q$ 个查询 $(x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q)$。

对每个 $i = 1, 2, \ldots, Q$,$x_i$ 是满足 $1 \le x_i \le 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$ 取模。

输入格式

输入按以下格式从标准输入给出:

N Q
S
x_1 c_1
x_2 c_2
⋮
x_Q c_Q

输出格式

输出 $Q$ 行。对每个 $i = 1, 2, \ldots, Q$,第 $i$ 行输出第 $i$ 个查询 $(x_i, c_i)$ 的答案(即题述第 2 步中,对 $998244353$ 取模后的字符串个数)。

样例

3 3
100
2 1
2 ?
3 ?

5
7
10

第 1 个查询首先把 $S$ 改为 110。可以以 $S =$ 110 的子序列得到的字符串有 0, 1, 10, 11, 110 共 5 个。因此,第 1 个查询的答案为 5。

第 2 个查询首先把 $S$ 改为 1?0。$S =$ 1?0 中的 ? 可以替换出 100 和 110 两种字符串。这些字符串之一的子序列可以得到的字符串有 0, 1, 00, 10, 11, 100, 110 共 7 个。因此,第 2 个查询的答案为 7。

第 3 个查询首先把 $S$ 改为 1??。$S =$ 1?? 中的 ? 可以替换出 100, 101, 110, 111 四种字符串。这些字符串之一的子序列可以得到的字符串有 0, 1, 00, 01, 10, 11, 100, 101, 110, 111 共 10 个。因此,第 3 个查询的答案为 10。

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

746884092
532460539
299568633
541985786
217532539
217532539
217532539
573323772
483176957
236273405

请务必输出对 $998244353$ 取模后的个数。

数据范围

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