F. 二进制子序列权值和

时间与内存限制

• 时间限制：$3$ 秒
• 内存限制：$256$ MB

定义

对于一个二进制字符串 $v$，定义它的得分为： 在所有 $i$（$0\le i\le |v|$）中，

$$F(v,1,i)\cdot F(v,i+1,|v|)$$

的最大值。

其中函数 $F$ 定义为：

$$F(v,l,r) = (r-l+1) - 2\cdot \operatorname{zero}(v,l,r) $$

$\operatorname{zero}(v,l,r)$ 表示子串 $v_lv_{l+1}\dots v_r$ 中 $0$ 的个数。 若 $l>r$，则 $F(v,l,r)=0$。

---

题目描述

给定一个长度为 $n$ 的二进制字符串 $s$，以及 $q$ 次询问。

每次询问给定一个位置 $i$（$1\le i\le n$），你需要翻转 $s_i$：

• $0$ 变 $1$
• $1$ 变 $0$

每次翻转后，你需要求出： 当前 $s$ 的所有非空子序列 $v$ 的得分之和，答案对 $998244353$ 取模。

修改是持久的，即每次翻转会保留到后续询问。

---

输入格式

第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例组数。

每组数据：

• 第一行两个整数 $n,q$（$1\le n,q\le 2\times 10^5$）。
• 第二行一个长度为 $n$ 的二进制字符串 $s$。
• 接下来 $q$ 行，每行一个整数 $i$，表示翻转第 $i$ 位。

保证所有测试用例的 $\sum n$ 与 $\sum q$ 均不超过 $2\times 10^5$。

---

输出格式

对于每次询问，输出一行一个整数，表示所有非空子序列的得分之和对 $998244353$ 取模的结果。

---

样例输入

3
3 2
010
1
3
10 3
0101000110
3
5
10
24 1
011001100110000101111000
24

样例输出

1
5
512
768
1536
23068672

---

样例解释（第一个测试用例）

第一次翻转后 $s=110$。 枚举所有非空子序列并计算得分，总和为 $1$。

第二次翻转后 $s=111$。 各子序列得分分别为： $0,0,1,0,1,1,2$，总和为 $5$。