Kuvaus
Annettuna on pituutta $N$ oleva merkkijono $S$, joka koostuu isoista englantilaisista kirjaimista. Voit suorittaa merkkijonolle $S$ seuraavan operaation mielivaltaisen monta kertaa:
- Valitse kokonaislukunelikko $(i, j, k, l)$ siten, että $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ ja $S_l = \text{C}$. Korvaa kaikki merkit $S_i, S_j, S_k, S_l$ merkillä $\text{X}$ ja ansaitse $(i \times j \times k \times l)$ jeniä.
Etsi suurin mahdollinen kokonaismäärä rahaa, joka voidaan ansaita, modulo $998244353$.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $N$ ($1 \le N \le 5 \times 10^5$). Toinen rivi sisältää pituutta $N$ olevan merkkijonon $S$, joka koostuu isoista englantilaisista kirjaimista.
Tuloste
Tulosta vastaus.
Esimerkit
Syöte 1
10 KKUPCUCAPC
Tuloste 1
1164
Syöte 2
4 TUNA
Tuloste 2
0
Syöte 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Tuloste 3
619704
Huomautus
Huomaa, että sinua pyydetään ilmoittamaan suurimman arvon jakojäännös, ei suurinta mahdollista jakojäännöstä. Ensimmäisessä esimerkissä voit ansaita 1164 jeniä suorittamalla seuraavat operaatiot:
- Valitse $(i, j, k, l) = (1, 3, 4, 7)$. Ansaitset $1 \times 3 \times 4 \times 7 = 84$ jeniä. Tällöin $S = \text{XKXXCUXAPC}$.
- Valitse $(i, j, k, l) = (2, 6, 9, 10)$. Ansaitset $2 \times 6 \times 9 \times 10 = 1080$ jeniä. Tällöin $S = \text{XXXXCXXXAXX}$.
Voidaan todistaa, että on mahdotonta ansaita enemmän kuin 1164 jeniä, joten tulosta 1164. Toisessa esimerkissä operaatiota ei voida suorittaa kertaakaan, joten tulosta 0.