Considera una cadena de longitud $N$. Sea $S$ esa cadena repetida $K$ veces. Te interesa saber qué tan "wack" es la cadena, por lo que tu tarea es encontrar la WAC-ness de esta cadena.

La WAC-ness de una cadena es el número de veces que "WAC" aparece como subsecuencia de esa cadena.

Una subsecuencia de una cadena es una cadena que puede derivarse de la secuencia dada eliminando cero o más caracteres sin cambiar el orden de los caracteres restantes. Dos subsecuencias son diferentes si al menos uno de los índices restantes es diferente. Por ejemplo, en la cadena "AABC", la subsecuencia formada por los índices 1, 3 y 4 es distinta de la subsecuencia formada por los índices 2, 3 y 4.

Como la respuesta puede ser muy grande, por favor imprime la respuesta módulo 998 244 353.

Entrada

La primera línea contendrá dos enteros, $N$ y $K$ ($1 \le N \le 200\,000$, $1 \le K \le 200\,000$), la longitud de la cadena original y el número de veces que esa cadena se repite para formar $S$. La segunda y última línea contendrá la cadena original de $N$ caracteres, que consiste en letras mayúsculas del alfabeto inglés.

Salida

Imprime la WAC-ness de la cadena $S$ módulo 998 244 353.

Ejemplos

Entrada 1

5 1
WABCA

Salida 1

1

Entrada 2

5 2
WABCA

Salida 2

5