题目描述

题目译自 PA 2025 Runda 5 Podciągi

你有一个长度为 $n$ 的字符串 $s$，由字母集 $\{\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}, \texttt{e}, \texttt{f}\}$ 组成。接下来会对它进行 $q$ 次操作，每次操作是替换字符串中的一个字母。

考虑字符串 $s$ 的所有子序列集合 $X_s$，也就是通过删除某些字母后得到的所有可能字符串（多重集）。

你的任务是跟踪一个信息：在 $X_s$ 中，有多少不同的非空字符串 $t$ 至少出现了两次。

比如，对于字符串 $\texttt{ababa}$，有 $6$ 个这样的字符串 $t$：

• 字符串 $\texttt{a}$ 在 $X_s$ 中出现 $3$ 次。
• 字符串 $\texttt{b}$ 在 $X_s$ 中出现 $2$ 次。
• 字符串 $\texttt{ab}$ 在 $X_s$ 中出现 $3$ 次（分别删去位置 $3,4,5$；$2,3,5$ 或 $1,2,5$ 的字母）。
• 字符串 $\texttt{ba}$ 在 $X_s$ 中出现 $3$ 次（分别删去位置 $1,4,5$；$1,3,4$ 或 $1,2,3$ 的字母）。
• 字符串 $\texttt{aa}$ 在 $X_s$ 中出现 $3$ 次（分别删去位置 $2,4,5$；$2,3,4$ 或 $1,2,4$ 的字母）。
• 字符串 $\texttt{aba}$ 在 $X_s$ 中出现 $4$ 次（分别删去位置 $4,5$；$3,4$；$2,3$ 或 $1,2$ 的字母）。

请你算出初始字符串 $s$ 以及每次操作后 $s$ 的 $X_s$ 中符合条件的字符串 $t$ 的数量。因为这些数字可能很大，输出它们对 $998244353$ 取模的结果。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($3 \leq n \leq 50000$, $0 \leq q \leq 50000$)，分别表示字符串长度和操作次数。

第二行是一个长度为 $n$ 的字符串，仅由小写字母 $\texttt{a}$ 到 $\texttt{f}$ 组成。

接下来的 $q$ 行描述操作，每行包含一个整数 $p_i$ ($1 \leq p_i \leq n$) 和一个字母 $z_i$ ($z_i \in \{\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}, \texttt{e}, \texttt{f}\}$)，表示将 $s$ 中第 $p_i$ 位置的字母替换为 $z_i$。

输出格式

输出 $q+1$ 行，每行一个整数。第 $i$ 行表示初始状态或前 $i-1$ 次操作后的 $s$ 中，$X_s$ 内至少出现两次的不同字符串 $t$ 的数量，结果对 $998244353$ 取模。

样例

输入：

4 3
abca
1 a
4 d
2 c

输出：

1
1
0
4

以下是字符串 $s$ 在每次更新后的状态，以及作为 $s$ 子序列至少出现两次的字符串 $t$：

• 初始字符串：$\texttt{abca}$，符合条件的子序列：$\{\texttt{a}\}$
• 第一次操作后：$\texttt{abca}$（不变），符合条件的子序列：$\{\texttt{a}\}$
• 第二次操作后：$\texttt{abcd}$，符合条件的子序列：$\{\}$
• 第三次操作后：$\texttt{accd}$，符合条件的子序列：$\{\texttt{a}, \texttt{c}, \texttt{ac}, \texttt{cc}\}$