问题 D: another 子序列问题
内存限制：1024 MB
时间限制：6.000 S
评测方式：文本比较
命题人：
提交：5
解决：5
题目描述
给定一个长为 $N$ 的字符串 $S$ 只含 '0', '1', '?' 三个字符，有 $Q$ 次操作，每次操作一个整数 $x$ 和一个字符 $c$，需要将 $S_x$ 改为 $c$ 后输出整个字符串不同的子序列个数对 $998244353$ 取模后的结果
'?' 代表既可以是 ‘1’ 也可以是 ‘0’，例如字符串"1?" 的子序列个数为 $4$
'?' 代表既可以是 ‘1’ 也可以是 ‘0’，例如字符串"1?" 的子序列个数为 $4$
输入
第一行两个整数 $1 \le N, Q \le 10^5$ 代表字符串 $S$ 的长度
第二行为字符串 $S$
接下来 $Q$ 行每行一个整数 $1 \le x \le n$ 和一个字符 $c \in \{0, 1, ?\}$
第二行为字符串 $S$
接下来 $Q$ 行每行一个整数 $1 \le x \le n$ 和一个字符 $c \in \{0, 1, ?\}$
输出
输出一个整数表示整个字符串不同子序列的个数 对 $998244353$ 取模后的结果并换行
样例输入 复制
3 3
100
2 1
2 ?
3 ?样例输出 复制
5
7
10