给定一个长度为 $n$ 的字符串 $s$，其字符集为 $\{a, b, c, d, e, f\}$。该字符串将进行 $q$ 次操作，每次操作修改字符串中的恰好一个字符。

考虑 $s$ 的所有子序列构成的多重集 $X_s$（即通过从 $s$ 中删除某些字符所得到的字符串集合）。

你的任务是维护不同非空字符串 $t$ 的数量，使得 $t$ 在 $X_s$ 中至少出现两次。

例如，在字符串 ababa 中，有 6 个这样的字符串： 字符串 a 在 $X_s$ 中出现 3 次。 字符串 b 在 $X_s$ 中出现 2 次。 字符串 ab 在 $X_s$ 中出现 3 次（通过删除 $s$ 中位置为 3, 4, 5；2, 3, 5 或 1, 2, 5 的字符得到）。 字符串 ba 在 $X_s$ 中出现 3 次（通过删除 $s$ 中位置为 1, 4, 5；1, 3, 4 或 1, 2, 3 的字符得到）。 字符串 aa 在 $X_s$ 中出现 3 次（通过删除 $s$ 中位置为 2, 4, 5；2, 3, 4 或 1, 2, 4 的字符得到）。 字符串 aba 在 $X_s$ 中出现 4 次（通过删除 $s$ 中位置为 4, 5；3, 4；2, 3 或 1, 2 的字符得到）。

请计算初始字符串 $s$ 以及每次操作后，满足上述条件的字符串 $t$ 的数量。由于结果可能很大，请输出其对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($3 \le n \le 50\,000, 0 \le q \le 50\,000$)，其中 $n$ 表示字符串长度，$q$ 表示操作次数。

第二行包含一个长度为 $n$ 的字符串，由小写英文字母组成。该字符串仅包含从 a 到 f 的字符。

接下来的 $q$ 行描述了操作。每行包含一个整数 $p_i$ ($1 \le p_i \le n$) 和一个字符 $z_i$ ($z_i \in \{a, b, c, d, e, f\}$)，表示将字符串 $s$ 中位置 $p_i$ 处的字符修改为 $z_i$。

输出格式

输出应包含 $q + 1$ 行；第 $i$ 行应包含一个整数：在字符串 $s$ 中作为子序列至少出现两次的不同字符串 $t$ 的数量。所有结果均需对 $998\,244\,353$ 取模。

样例

输入 1

4 3
abca
1 a
4 d
2 c

输出 1

1
1
0
4

说明 1

样例说明：以下是字符串 $s$ 在每次更新后的状态，以及在 $s$ 中作为子序列至少出现两次的字符串 $t$： 字符串：abca，子序列：{a} 字符串：abca，子序列：{a} 字符串：abcd，子序列：{} 字符串：accd，子序列：{ac, acd, cd, c}

子任务

在分值非零的测试点中，原始字符串及所有操作仅使用字符 a 和 b。