当前没有测试数据。

Ex - 01? 查询

得分 : $600$ 分

问题描述

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

还给定 $Q$ 个查询 $(x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q)$。
对于每个 $i = 1, 2, \ldots, Q$，都满足 $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 所得到的非空子序列数，结果对 $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$ 行应该包含答案，对于查询 $(x_i, c_i)$ （也就是第 2 步骤中的字符串数，结果对 $998244353$ 取模）。

3 3
100
2 1
2 ?
3 ?

5
7
10

• 第 1 个查询将 $S$ 改为 110。能够从 $S = $ 110 得到 5 个字符串的子序列：0、1、10、11、110。因此，第 1 个查询的答案为 5。

• 第 2 个查询将 $S$ 改为 1?0。能够从 $S = $ 1?0 得到 2 个子字符串的：100 和 110。能够从这些字符串分别得到 7 个子序列：0、1、00、10、11、100、110。因此，第 2 个查询的答案为 7。

• 第 3 个查询将 $S$ 改为 1??。能够从 $S = $ 1?? 得到 4 个子字符串：100、101、110、111。能够从这些字符串分别得到 10 个子序列：0、1、00、01、10、11、100、101、110、111。因此，第 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$。