Lýsing
Gefinn er strengur $S$ af lengd $N$ sem samanstendur af enskum hástöfum. Þú mátt framkvæma eftirfarandi aðgerð á $S$ hversu oft sem er:
- Veldu fjórðung af fjórum heiltölum $(i, j, k, l)$ þannig að $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}$. Skiptu öllum $S_i, S_j, S_k, S_l$ út fyrir $\text{X}$ og þénaðu $(i \times j \times k \times l)$ jen.
Finndu hámarksfjárhæðina sem hægt er að þéna samtals, modulo $998244353$.
Inntak
Fyrsta línan inniheldur heiltölu $N$ ($1 \le N \le 5 \times 10^5$). Önnur línan inniheldur streng $S$ af lengd $N$ sem samanstendur af enskum hástöfum.
Úttak
Prentaðu svarið.
Dæmi
Inntak 1
10 KKUPCUCAPC
Úttak 1
1164
Inntak 2
4 TUNA
Úttak 2
0
Inntak 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Úttak 3
619704
Athugasemd
Athugaðu að beðið er um afganginn af hámarksgildinu, ekki mesta mögulega afganginn. Í fyrsta dæminu geturðu þénað 1164 jen með því að framkvæma eftirfarandi aðgerðir:
- Veldu $(i, j, k, l) = (1, 3, 4, 7)$. Þú þénar $1 \times 3 \times 4 \times 7 = 84$ jen. Þá er $S = \text{XKXXCUXAPC}$.
- Veldu $(i, j, k, l) = (2, 6, 9, 10)$. Þú þénar $2 \times 6 \times 9 \times 10 = 1080$ jen. Þá er $S = \text{XXXXCXXXAXX}$.
Sanna má að ómögulegt sé að þéna meira en 1164 jen, svo prentaðu 1164. Í öðru dæminu er ekki hægt að framkvæma neina aðgerð einu sinni, svo prentaðu 0.