Рассмотрим строку длины $N$. Пусть строка $S$ — это данная строка, повторенная $K$ раз. Вас интересует, насколько «wack» (странной) является эта строка, поэтому ваша задача — найти WAC-ness этой строки.

WAC-ness строки — это количество вхождений «WAC» в качестве подпоследовательности этой строки.

Подпоследовательность строки — это строка, которую можно получить из данной последовательности путем удаления нуля или более символов без изменения порядка оставшихся символов. Две подпоследовательности считаются различными, если различается хотя бы один из индексов оставшихся символов. Например, в строке «AABC» подпоследовательность, образованная индексами 1, 3 и 4, отличается от подпоследовательности, образованной индексами 2, 3 и 4.

Так как ответ может быть очень большим, выведите его по модулю $998\,244\,353$.

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

В первой строке содержатся два целых числа $N$ и $K$ ($1 \le N \le 200\,000$, $1 \le K \le 200\,000$), длина исходной строки и количество повторений этой строки для формирования $S$. Во второй и последней строке содержится исходная строка из $N$ символов, состоящая из заглавных букв английского алфавита.

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

Выведите WAC-ness строки $S$ по модулю $998\,244\,353$.

Примеры

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

5 1
WABCA

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

1

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

5 2
WABCA

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

5