Description
There is a string $S$ of length $N$ consisting of uppercase English letters. You may perform the following operation on $S$ any number of times:
- Choose a quadruple of integers $(i, j, k, l)$ such that $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$, and $S_l = \text{C}$. Replace all of $S_i, S_j, S_k, S_l$ with $\text{X}$, and earn $(i \times j \times k \times l)$ yen.
Find the maximum amount of money that can be earned in total, modulo $998244353$.
Input
The first line contains an integer $N$ ($1 \le N \le 5 \times 10^5$). The second line contains a string $S$ of length $N$ consisting of uppercase English letters.
Output
Print the answer.
Examples
Input 1
10 KKUPCUCAPC
Output 1
1164
Input 2
4 TUNA
Output 2
0
Input 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Output 3
619704
Note
Note that you are asked for the remainder of the maximum value, not the maximum possible remainder. For the first example, you can earn 1164 yen by performing the following operations:
- Choose $(i, j, k, l) = (1, 3, 4, 7)$. You earn $1 \times 3 \times 4 \times 7 = 84$ yen. Then $S = \text{XKXXCUXAPC}$.
- Choose $(i, j, k, l) = (2, 6, 9, 10)$. You earn $2 \times 6 \times 9 \times 10 = 1080$ yen. Then $S = \text{XXXXCXXXAXX}$.
It can be proven that it is impossible to earn more than 1164 yen, so print 1164. For the second example, no operation can be performed even once, so print 0.