[ABC246Ex] 01? Queries

给定长度为 $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$。

[problemUrl]: https://atcoder.jp/contests/abc246/tasks/abc246_h `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 $ で割ったあまり）を出力せよ。

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