Beskrivning
Det finns en sträng $S$ av längd $N$ som består av stora engelska bokstäver. Du får utföra följande operation på $S$ valfritt antal gånger:
- Välj en kvadrupel av heltal $(i, j, k, l)$ sådan att $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ och $S_l = \text{C}$. Ersätt alla $S_i, S_j, S_k, S_l$ med $\text{X}$, och tjäna $(i \times j \times k \times l)$ yen.
Hitta den maximala summan pengar som kan tjänas totalt, modulo $998244353$.
Indata
Den första raden innehåller ett heltal $N$ ($1 \le N \le 5 \times 10^5$). Den andra raden innehåller en sträng $S$ av längd $N$ som består av stora engelska bokstäver.
Utdata
Skriv ut svaret.
Exempel
Indata 1
10 KKUPCUCAPC
Utdata 1
1164
Indata 2
4 TUNA
Utdata 2
0
Indata 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Utdata 3
619704
Anmärkning
Observera att du efterfrågas resten av det maximala värdet, inte den maximalt möjliga resten. För det första exemplet kan du tjäna 1164 yen genom att utföra följande operationer:
- Välj $(i, j, k, l) = (1, 3, 4, 7)$. Du tjänar $1 \times 3 \times 4 \times 7 = 84$ yen. Då blir $S = \text{XKXXCUXAPC}$.
- Välj $(i, j, k, l) = (2, 6, 9, 10)$. Du tjänar $2 \times 6 \times 9 \times 10 = 1080$ yen. Då blir $S = \text{XXXXCXXXAXX}$.
Det kan bevisas att det är omöjligt att tjäna mer än 1164 yen, så skriv ut 1164. För det andra exemplet kan ingen operation utföras ens en gång, så skriv ut 0.