L. Make Many KUPC
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \leq i \lt j \lt k \lt l \leq \lvert S \rvert$$$, $$$S_i=$$$ K, $$$S_j=$$$ U, $$$S_k=$$$ P, and $$$S_l=$$$ C. Replace all of $$$S_i,S_j,S_k,S_l$$$ with 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 \leq N \leq 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
10
KKUPCUCAPC
Output
1164
Input
4
TUNA
Output
0
Input
30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Output
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 =$$$ XKXXCUXAPC.
  • Choose $$$(i,j,k,l) = (2,6,9,10)$$$. You earn $$$2 \times 6 \times 9 \times 10 = 1080$$$ yen. Then $$$S =$$$ 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$$$.