Se tiene una cadena $S$ de longitud $N$ que consiste en letras inglesas mayúsculas. Puedes realizar la siguiente operación sobre $S$ cualquier número de veces:
- Elige una cuádrupla de enteros $(i, j, k, l)$ tal que $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ y $S_l = \text{C}$. Reemplaza todos los caracteres $S_i, S_j, S_k, S_l$ con $\text{X}$ y gana $(i \times j \times k \times l)$ yenes.
Encuentra la cantidad máxima de dinero que se puede ganar en total, módulo 998244353.
Entrada
La primera línea contiene un entero $N$ ($1 \le N \le 5 \times 10^5$).
La segunda línea contiene una cadena $S$ de longitud $N$ que consiste en letras inglesas mayúsculas.
Salida
Imprime la respuesta.
Ejemplos
Entrada 1
10 KKUPCUCAPC
Salida 1
1164
Entrada 2
4 TUNA
Salida 2
0
Entrada 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Salida 3
619704
Nota
Ten en cuenta que se te pide el resto del valor máximo, no el máximo resto posible.
Para el primer ejemplo, puedes ganar 1164 yenes realizando las siguientes operaciones:
- Elige $(i, j, k, l) = (1, 3, 4, 7)$. Ganas $1 \times 3 \times 4 \times 7 = 84$ yenes. Entonces $S = \text{XKXXCUXAPC}$.
- Elige $(i, j, k, l) = (2, 6, 9, 10)$. Ganas $2 \times 6 \times 9 \times 10 = 1080$ yenes. Entonces $S = \text{XXXXCXXXAXX}$.
Se puede demostrar que es imposible ganar más de 1164 yenes, por lo tanto, imprime 1164.
Para el segundo ejemplo, no se puede realizar ninguna operación ni una sola vez, por lo tanto, imprime 0.