給定一個長度為 $n$ 的字串 $s$，其字母表為 $\{a, b, c, d, e, f\}$。我們將對此字串執行 $q$ 次操作，每次操作皆為修改字串中的某一個字元。

考慮 $X_s$ 為 $s$ 的所有子序列所構成的多重集（即透過刪除 $s$ 中某些字元所產生的所有字串）。

你的任務是維護並輸出在 $X_s$ 中出現至少兩次的相異非空字串 $t$ 的數量。

例如，在字串 ababa 中，有 6 個這樣的字串： 字串 a 在 $X_s$ 中出現三次。 字串 b 在 $X_s$ 中出現兩次。 字串 ab 在 $X_s$ 中出現三次（分別刪除 $s$ 中位置 3, 4, 5；2, 3, 5 或 1, 2, 5 的字元）。 字串 ba 在 $X_s$ 中出現三次（分別刪除 $s$ 中位置 1, 4, 5；1, 3, 4 或 1, 2, 3 的字元）。 字串 aa 在 $X_s$ 中出現三次（分別刪除 $s$ 中位置 2, 4, 5；2, 3, 4 或 1, 2, 4 的字元）。 字串 aba 在 $X_s$ 中出現四次（分別刪除 $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

說明

• 初始狀態：abca，滿足條件的字串 $t$ 為：{a}，共 1 個。
• 操作 1 (1 a)：字串變為 abca，滿足條件的字串 $t$ 為：{a}，共 1 個。
• 操作 2 (4 d)：字串變為 abcd，滿足條件的字串 $t$ 為：{}，共 0 個。
• 操作 3 (2 c)：字串變為 accd，滿足條件的字串 $t$ 為：{c, ac, cd, acd}，共 4 個。

在某些測試資料中，原始字串及所有操作僅使用字母 a 與 b。