Beskrivelse
Det er gitt en streng $S$ med lengde $N$ som består av store engelske bokstaver. Du kan utføre følgende operasjon på $S$ så mange ganger du vil:
- Velg en kvadruppel av heltall $(i, j, k, l)$ slik at $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ og $S_l = \text{C}$. Erstatt alle $S_i, S_j, S_k, S_l$ med $\text{X}$, og tjen $(i \times j \times k \times l)$ yen.
Finn det maksimale pengebeløpet som kan tjenes totalt, modulo $998244353$.
Inndata
Den første linjen inneholder et heltall $N$ ($1 \le N \le 5 \times 10^5$). Den andre linjen inneholder en streng $S$ med lengde $N$ som består av store engelske bokstaver.
Utdata
Skriv ut svaret.
Eksempler
Inndata 1
10 KKUPCUCAPC
Utdata 1
1164
Inndata 2
4 TUNA
Utdata 2
0
Inndata 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Utdata 3
619704
Merk
Merk at du blir bedt om resten av den maksimale verdien, ikke den maksimalt mulige resten. For det første eksempelet kan du tjene 1164 yen ved å utføre følgende operasjoner:
- Velg $(i, j, k, l) = (1, 3, 4, 7)$. Du tjener $1 \times 3 \times 4 \times 7 = 84$ yen. Da blir $S = \text{XKXXCUXAPC}$.
- Velg $(i, j, k, l) = (2, 6, 9, 10)$. Du tjener $2 \times 6 \times 9 \times 10 = 1080$ yen. Da blir $S = \text{XXXXCXXXAXX}$.
Det kan bevises at det er umulig å tjene mer enn 1164 yen, så skriv ut 1164. For det andre eksempelet kan ingen operasjon utføres engang én gang, så skriv ut 0.