Опис
Дано рядок $S$ довжини $N$, що складається з великих латинських літер. Ви можете виконати над $S$ таку операцію довільну кількість разів:
- Виберіть четвірку цілих чисел $(i, j, k, l)$ таку, що $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ та $S_l = \text{C}$. Замініть усі символи $S_i, S_j, S_k, S_l$ на $\text{X}$ та отримайте $(i \times j \times k \times l)$ єн.
Знайдіть максимальну суму грошей, яку можна заробити загалом, за модулем $998244353$.
Вхідні дані
Перший рядок містить ціле число $N$ ($1 \le N \le 5 \times 10^5$). Другий рядок містить рядок $S$ довжини $N$, що складається з великих латинських літер.
Вихідні дані
Виведіть відповідь.
Приклади
Вхідні дані 1
10 KKUPCUCAPC
Вихідні дані 1
1164
Вхідні дані 2
4 TUNA
Вихідні дані 2
0
Вхідні дані 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Вихідні дані 3
619704
Примітка
Зверніть увагу, що потрібно знайти остачу від максимального значення, а не максимально можливу остачу. У першому прикладі можна заробити 1164 єни, виконавши такі операції:
- Виберіть $(i, j, k, l) = (1, 3, 4, 7)$. Ви отримаєте $1 \times 3 \times 4 \times 7 = 84$ єни. Тоді $S = \text{XKXXCUXAPC}$.
- Виберіть $(i, j, k, l) = (2, 6, 9, 10)$. Ви отримаєте $2 \times 6 \times 9 \times 10 = 1080$ єн. Тоді $S = \text{XXXXCXXXAXX}$.
Можна довести, що заробити більше ніж 1164 єни неможливо, тому виведіть 1164. У другому прикладі жодну операцію не можна виконати навіть один раз, тому виведіть 0.