题目背景

PA 2025 R5B.

警告：滥用本题评测一次即可封号。

题目描述

本题中下标均为 $\text{1-indexed}$。

给定长度为 $n$ 的字符串 $s$，字符集 $\Sigma=\{\texttt{a},\texttt{b},\ldots,\texttt{f}\}$。

有 $q$ 次操作，每次操作对 $s$ 进行单点修改。

对于 $i=1,2,\ldots,q+1$，求出：进行前 $(i-1)$ 次操作后，$s$ 中满足以下条件的非空子序列 $t$ 的数量：

• $t$ 在 $s$ 中出现至少两次。

由于答案可能很大，只需要求出答案对 $998\, 244\, 353$ 取模后的结果。

输入格式

第一行，两个非负整数 $n,q$。

第二行，字符串 $s$。

接下来 $q$ 行，第 $i$ 行正整数 $p_i$ 和字符 $c_i$，表示一次操作 $s_{p_i}\gets c_i$。

输出格式

输出 $(q+1)$ 行，第 $i$ 行一个非负整数，表示进行前 $(i-1)$ 次操作后的答案对 $998\, 244\, 353$ 取模后的结果。

4 3
abca
1 a
4 d
2 c

1
1
0
4

提示

样例解释

• 初始字符串为 $s=\texttt{abca}$，唯一符合条件的子序列为 $\texttt{a}$。
• 进行 $1$ 次操作后，字符串为 $s=\texttt{abca}$，唯一符合条件的子序列为 $\texttt{a}$。
• 进行前 $2$ 次操作后，字符串为 $s=\texttt{abcd}$，无符合条件的子序列。
• 进行前 $3$ 次操作后，$s=\texttt{accd}$，符合条件的子序列有 $\texttt{ac},\texttt{cd},\texttt{acd},\texttt{c}$。

子任务

存在大于 $0$ 分的子任务满足 $\Sigma=\{\texttt{a},\texttt{b}\}$。

数据范围

• $3 \le n \le 5\times 10^4$；
• $0 \le q \le 5\times 10^4$；
• $s_i,c_i\in \Sigma=\{\texttt{a},\texttt{b},\ldots,\texttt{f}\}$；
• $1\le p_i\le n$。