配点 : $600$ 点

問題文

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$ で割ったあまりを出力する。

制約

• $1 \leq N, Q \leq 10^5$
• $N, Q$ は整数
• $S$ は 0 、1 、? のみからなる長さ $N$ の文字列
• $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$ で割ったあまり）を出力せよ。

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 の ? を 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$ を出力します。

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$ で割ったあまりを出力することに注意してください。