Descrizione
C'è una stringa $S$ di lunghezza $N$ composta da lettere maiuscole dell'alfabeto inglese. Puoi eseguire la seguente operazione su $S$ un numero qualsiasi di volte:
- Scegli una quadrupla di interi $(i, j, k, l)$ tale che $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ e $S_l = \text{C}$. Sostituisci tutti gli elementi $S_i, S_j, S_k, S_l$ con $\text{X}$, e guadagna $(i \times j \times k \times l)$ yen.
Trova la quantità massima di denaro che può essere guadagnata in totale, modulo $998244353$.
Input
La prima riga contiene un intero $N$ ($1 \le N \le 5 \times 10^5$). La seconda riga contiene una stringa $S$ di lunghezza $N$ composta da lettere maiuscole dell'alfabeto inglese.
Output
Stampa la risposta.
Esempi
Input 1
10 KKUPCUCAPC
Output 1
1164
Input 2
4 TUNA
Output 2
0
Input 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Output 3
619704
Note
Nota che ti viene chiesto il resto del valore massimo, non il massimo resto possibile. Per il primo esempio, puoi guadagnare 1164 yen eseguendo le seguenti operazioni:
- Scegli $(i, j, k, l) = (1, 3, 4, 7)$. Guadagni $1 \times 3 \times 4 \times 7 = 84$ yen. Allora $S = \text{XKXXCUXAPC}$.
- Scegli $(i, j, k, l) = (2, 6, 9, 10)$. Guadagni $2 \times 6 \times 9 \times 10 = 1080$ yen. Allora $S = \text{XXXXCXXXAXX}$.
Si può dimostrare che è impossibile guadagnare più di 1164 yen, quindi stampa 1164. Per il secondo esempio, non è possibile eseguire alcuna operazione nemmeno una volta, quindi stampa 0.