题目描述

给你一个长度为 $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. 首先，将 $x_i$ -th 字符从 $S$ 的开头改为 $c_i$ 。
2. 然后，打印在将 $S$ 中出现的每个 ? 分别替换为 0 或 1 之后，作为 $S$ 的子序列（不一定连续）的非空字符串的个数，模数为 $998244353$ 。

输入格式

第一行输入 $N$ $Q$

第二行输入字符串 $S$

接下来 $Q$ 行每行两个分别是$x_i$ $c_i$

输出格式

输出一共输出 $Q$ 行

3 3
100
2 1
2 ?
3 ?

5
7
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

样例 1 解释

• 第 $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$ 。

提示

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