Дана строка $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

Примечание

Для первого примера вы можете заработать 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.

Входные данные 2

4
TUNA

Выходные данные 2

0

Примечание

Для второго примера нельзя выполнить ни одной операции, поэтому выведите 0.

Входные данные 3

30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK

Выходные данные 3

619704

Примечание

Обратите внимание, что от вас требуется найти остаток от максимального значения, а не максимально возможный остаток.