题目描述

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 、? のうちのいずれかの文字です。

$i\ =\ 1,\ 2,\ \ldots,\ Q$ の順に、クエリ $(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$ で割ったあまり）を出力せよ。

题目大意

给定长度为 $N$ 的仅包含 0，1，? 的字符串 $S$，给定 $Q$ 组询问 $(x_1, c_1), (x_2, c_2), \cdots, (x_q, c_q)$，每次将原字符串中 $x_i$ 位置的字符改为 $c_i$，然后输出 $S$ 有多少种非空子序列，? 需任意替换为 0 或 1。

$1 \le N, Q \le 10^5, 1 \le x_i \le N$。

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\ \leq\ N,\ Q\ \leq\ 10^5$
• $N,\ Q$ は整数
• $S$ は 0 、1 、? のみからなる長さ $N$ の文字列
• $1\ \leq\ x_i\ \leq\ N$
• $c_i$ は 0 、1 、? のうちいずれかの文字

Sample Explanation 1

- $1$ 個目のクエリで、まず $S\ =$ 110 に変更されます。$S\ =$ 110 の部分列としてあり得る文字列は、0 、1 、10 、11 、110 の $5$ 個です。よって、$1$ 個目のクエリに対する答えとして $5$ を出力します。 - $2$ 個目のクエリで、まず $S\ =$ 1?0 に変更されます。$S\ =$ 1?0 の ? を 0 または 1 に置き換えて得られる文字列は、100 と 110 の $2$ つです。 これらのどちらかの部分列としてあり得る文字列は、0 、1 、00 、10 、11 、100 、110 の $7$ 個です。よって、$2$ 個目のクエリに対する答えとして $7$ を出力します。 - $3$ 個目のクエリで、まず $S\ =$ 1?? に変更されます。$S\ =$ 1?? の ? を 0 または 1 に置き換えて得られる文字列は、100、 101、 110、 111 の $4$ つです。 これらのいずれかの部分列としてあり得る文字列は、0 、1 、00 、01 、10 、11 、100 、101 、110 、111 の $10$ 個です。よって、$3$ 個目のクエリに対する答えとして $10$ を出力します。

Sample Explanation 2

$998244353$ で割ったあまりを出力することに注意してください。