Dany jest ciąg $S$ o długości $N$ składający się z wielkich liter alfabetu angielskiego. Możesz wykonać następującą operację na $S$ dowolną liczbę razy:

• Wybierz czwórkę liczb całkowitych $(i, j, k, l)$ takich, że $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$ oraz $S_l = \text{C}$. Zastąp wszystkie znaki $S_i, S_j, S_k, S_l$ znakiem $\text{X}$ i zarób $(i \times j \times k \times l)$ jenów.

Znajdź maksymalną łączną kwotę pieniędzy, jaką można zarobić, modulo $998244353$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $N$ ($1 \le N \le 5 \times 10^5$). Druga linia zawiera ciąg $S$ o długości $N$ składający się z wielkich liter alfabetu angielskiego.

Wyjście

Wypisz odpowiedź.

Przykład

Wejście 1

10
KKUPCUCAPC

Wyjście 1

1164

Wejście 2

4
TUNA

Wyjście 2

0

Wejście 3

30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK

Wyjście 3

619704

Uwagi

Zwróć uwagę, że pytamy o resztę z dzielenia wartości maksymalnej, a nie o maksymalną możliwą resztę.

Dla pierwszego przykładu można zarobić 1164 jeny, wykonując następujące operacje:

• Wybierz $(i, j, k, l) = (1, 3, 4, 7)$. Zarabiasz $1 \times 3 \times 4 \times 7 = 84$ jeny. Wtedy $S = \text{XKXXCUXAPC}$.
• Wybierz $(i, j, k, l) = (2, 6, 9, 10)$. Zarabiasz $2 \times 6 \times 9 \times 10 = 1080$ jenów. Wtedy $S = \text{XXXXCXXXAXX}$.

Można udowodnić, że nie da się zarobić więcej niż 1164 jeny, więc wypisujemy 1164.

Dla drugiego przykładu nie można wykonać żadnej operacji, więc wypisujemy 0.