Considérons une chaîne de longueur $N$. Soit $S$ cette chaîne répétée $K$ fois. Vous vous intéressez au degré de « wack » de la chaîne, votre tâche est donc de trouver le WAC-ness de cette chaîne.

Le WAC-ness d'une chaîne est le nombre de fois que « WAC » apparaît en tant que sous-séquence de cette chaîne.

Une sous-séquence d'une chaîne est une chaîne qui peut être dérivée de la séquence donnée en supprimant zéro ou plusieurs caractères sans changer l'ordre des caractères restants. Deux sous-séquences sont différentes si au moins l'un des indices restants est différent. Par exemple, dans la chaîne « AABC », la sous-séquence formée par les indices 1, 3 et 4 est distincte de la sous-séquence formée par les indices 2, 3 et 4.

Comme la réponse peut être très grande, veuillez afficher la réponse modulo $998\,244\,353$.

Entrée

La première ligne contiendra deux entiers, $N$ et $K$ ($1 \le N \le 200\,000$, $1 \le K \le 200\,000$), la longueur de la chaîne originale et le nombre de fois que cette chaîne est répétée pour former $S$. La deuxième et dernière ligne contiendra la chaîne originale de $N$ caractères, composée de lettres majuscules de l'alphabet anglais.

Sortie

Affichez le WAC-ness de la chaîne $S$ modulo $998\,244\,353$.

Exemples

Entrée 1

5 1
WABCA

Sortie 1

1

Entrée 2

5 2
WABCA

Sortie 2

5