Дано слово $s$ длины $n$ над алфавитом $\{a, b, c, d, e, f\}$. С этим словом будет выполнено $q$ операций. Каждая операция заключается в замене ровно одной буквы в слове.

Рассмотрим мультимножество $X_s$ всех подпоследовательностей $s$, то есть слов, полученных путем удаления некоторого подмножества букв из слова $s$.

Ваша задача — поддерживать информацию о количестве различных непустых слов $t$, которые встречаются в $X_s$ по крайней мере дважды.

Например, в строке 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).

Вычислите количество таких слов $t$ в множестве $X_s$ для начального слова $s$ и для слов $s$ после каждой из операций. Поскольку эти числа могут быть довольно большими, выведите их остатки от деления на $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\}$) и означает замену буквы на позиции $p_i$ в слове $s$ на букву $z_i$.

Выходные данные

На выходе должно быть $q + 1$ строк; в $i$-й строке должно находиться одно целое число: количество различных слов $t$, которые встречаются по крайней мере дважды как подпоследовательность слова $s$. Все результаты следует выводить по модулю $998\,244\,353$.

Примеры

Пример 1

4 3
abca
1 a
4 d
2 c

Выходные данные 1

1
1
0
4

Примечание

Пояснение к примеру: Вот состояние слова $s$ после последовательных обновлений и слов $t$, которые встречаются как подпоследовательность $s$ по крайней мере дважды: слово: abca, подпоследовательности: {a}, слово: abca, подпоследовательности: {a}, слово: abcd, подпоследовательности: {}, слово: accd, подпоследовательности: {ac, acd, cd, c}.

Подзадачи

В тестах, оцениваемых в некоторое ненулевое количество баллов, в исходном слове и во всех операциях используются только буквы a и b.