You are given a word $s$ of length $n$ over the alphabet $\{a, b, c, d, e, f\}$. There will be $q$ operations performed on this word. Each operation consists of changing exactly one letter in the word.

Consider the multiset $X_s$ of all subsequences of $s$, which are words formed by removing a subset of letters from $s$.

Your task is to maintain information about the number of distinct non-empty words $t$ that appear at least twice in $X_s$.

For example, in the string ababa, there are 6 such words: The word a appears in $X_s$ three times. The word b appears in $X_s$ two times. The word ab appears in $X_s$ three times (by removing letters at positions 3, 4, 5; 2, 3, 5; or 1, 2, 5). The word ba appears in $X_s$ three times (by removing letters at positions 1, 4, 5; 1, 3, 4; or 1, 2, 3). The word aa appears in $X_s$ three times (by removing letters at positions 2, 4, 5; 2, 3, 4; or 1, 2, 4). The word aba appears in $X_s$ four times (by removing letters at positions 4, 5; 3, 4; 2, 3; or 1, 2).

Calculate the number of such words $t$ in the set $X_s$ for the initial word $s$ and for the word $s$ after each operation. Since these numbers can be quite large, output their remainders modulo $998\,244\,353$.

Input

The first line of input contains two integers $n$ and $q$ ($3 \le n \le 50\,000$, $0 \le q \le 50\,000$), where $n$ is the length of the word and $q$ is the number of operations.

The second line of input contains an $n$-letter word consisting of lowercase English letters. This string consists only of letters from a to f.

The next $q$ lines contain descriptions of the operations. Each description consists of an integer $p_i$ ($1 \le p_i \le n$) and a letter $z_i$ ($z_i \in \{a, b, c, d, e, f\}$), meaning the letter at position $p_i$ in word $s$ is changed to letter $z_i$.

Output

The output should contain $q + 1$ lines; the $i$-th line should contain a single integer: the number of distinct words $t$ that appear at least twice as a subsequence of $s$. All results should be given modulo $998\,244\,353$.

Examples

Input 1

4 3
abca
1 a
4 d
2 c

Output 1

1
1
0
4

Note 1

Explanation of the example: Here is the state of the word $s$ after successive updates and the words $t$ that appear as a subsequence of $s$ at least twice: word: abca, subsequences: {a}, word: abca, subsequences: {a}, word: abcd, subsequences: {}, word: accd, subsequences: {ac, acd, cd, c}.

Subtasks

In tests worth a certain non-zero number of points, only the letters a and b are used in the original word and all operations.