Beschreibung
Gegeben ist eine Zeichenkette $S$ der Länge $N$, die aus englischen Großbuchstaben besteht. Sie können die folgende Operation beliebig oft auf $S$ anwenden:
- Wählen Sie ein Quadrupel ganzer Zahlen $(i, j, k, l)$ mit $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ und $S_l = \text{C}$. Ersetzen Sie alle Zeichen $S_i, S_j, S_k, S_l$ durch $\text{X}$ und erhalten Sie $(i \times j \times k \times l)$ Yen.
Bestimmen Sie den maximalen Geldbetrag, der insgesamt verdient werden kann, modulo $998244353$.
Eingabe
Die erste Zeile enthält eine ganze Zahl $N$ ($1 \le N \le 5 \times 10^5$). Die zweite Zeile enthält eine Zeichenkette $S$ der Länge $N$, die aus englischen Großbuchstaben besteht.
Ausgabe
Geben Sie die Antwort aus.
Beispiele
Eingabe 1
10 KKUPCUCAPC
Ausgabe 1
1164
Eingabe 2
4 TUNA
Ausgabe 2
0
Eingabe 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Ausgabe 3
619704
Hinweis
Beachten Sie, dass nach dem Rest des Maximalwerts gefragt ist, nicht nach dem maximal möglichen Rest. Im ersten Beispiel können Sie 1164 Yen verdienen, indem Sie die folgenden Operationen ausführen:
- Wählen Sie $(i, j, k, l) = (1, 3, 4, 7)$. Sie verdienen $1 \times 3 \times 4 \times 7 = 84$ Yen. Danach ist $S = \text{XKXXCUXAPC}$.
- Wählen Sie $(i, j, k, l) = (2, 6, 9, 10)$. Sie verdienen $2 \times 6 \times 9 \times 10 = 1080$ Yen. Danach ist $S = \text{XXXXCXXXAXX}$.
Es lässt sich beweisen, dass man nicht mehr als 1164 Yen verdienen kann; geben Sie daher 1164 aus. Im zweiten Beispiel kann keine Operation auch nur ein einziges Mal ausgeführt werden; geben Sie daher 0 aus.