Soit une chaîne $S$ de longueur $N$ composée de lettres majuscules anglaises. Vous pouvez effectuer l'opération suivante sur $S$ un nombre quelconque de fois :

• Choisir un quadruplet d'entiers $(i, j, k, l)$ tel que $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ et $S_l = \text{C}$. Remplacer tous les $S_i, S_j, S_k, S_l$ par $\text{X}$, et gagner $(i \times j \times k \times l)$ yens.

Trouvez le montant total maximum d'argent qui peut être gagné, modulo 998244353.

Entrée

La première ligne contient un entier $N$ ($1 \le N \le 5 \times 10^5$). La deuxième ligne contient une chaîne $S$ de longueur $N$ composée de lettres majuscules anglaises.

Sortie

Affichez la réponse.

Exemples

Entrée 1

10
KKUPCUCAPC

Sortie 1

1164

Remarque

Notez qu'il vous est demandé le reste de la valeur maximale, et non le reste maximum possible. Pour le premier exemple, vous pouvez gagner 1164 yens en effectuant les opérations suivantes :

• Choisir $(i, j, k, l) = (1, 3, 4, 7)$. Vous gagnez $1 \times 3 \times 4 \times 7 = 84$ yens. Alors $S = \text{XKXXCUXAPC}$.
• Choisir $(i, j, k, l) = (2, 6, 9, 10)$. Vous gagnez $2 \times 6 \times 9 \times 10 = 1080$ yens. Alors $S = \text{XXXXCXXXAXX}$.

Il peut être prouvé qu'il est impossible de gagner plus de 1164 yens, donc affichez 1164.

Entrée 2

4
TUNA

Sortie 2

0

Remarque

Pour le deuxième exemple, aucune opération ne peut être effectuée, donc affichez 0.

Entrée 3

30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK

Sortie 3

619704