L Make Many KUPC

制限時間: 2 sec メモリ制限: 1024 MB

Make Many KUPC

Statement

英大文字からなる長さ \(N\) の文字列 \(S\) があります。\(S\) に対して以下の操作を何回でも行うことができます。

\(1 \leq i \lt j \lt k \lt l \leq \lvert S \rvert, S_i=\) K, \(S_j=\) U, \(S_k=\) P, \(S_l=\) C なる整数の組\((i,j,k,l)\)を選ぶ。\(S_i,S_j,S_k,S_l\) をすべて X に置き換え、\((i \times j \times k \times l)\) 円得る。

最終的に得ることができる金額の最大値を \(998244353\) で割った余りを求めてください。

Input

\(1\) 行目に整数 \(N\) が与えられる。 ( \(1 \leq N \leq 5 \times 10^5\) )

\(2\) 行目に英大文字からなる長さ \(N\) の文字列 \(S\) が与えられる。

Output

答えを出力せよ。

Examples

Input 1

10
KKUPCUCAPC

Output 1

Input 2

4
TUNA

Output 2

Input 3

30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK

Output 3

Note

余りの最大値を求めるのではなく、最大値の余りを求めることに注意してください。

\(1\) つ目の入力について、以下の操作を行うことで \(1164\) 円得ることができます。

\((i,j,k,l) = (1,3,4,7)\) を選ぶ。\(1 \times 3 \times 4 \times 7 = 84\) 円を得る。\(S =\) XKXXCUXAPC となる。
\((i,j,k,l) = (2,6,9,10)\) を選ぶ。\(2 \times 6 \times 9 \times 10 = 1080\) 円を得る。\(S =\) XXXXCXXXAXX となる。

\(1164\) 円より多くの金額を得ることができないことが証明できるので \(1164\) を出力します。

\(2\) つ目の入力について、一回も操作ができないので \(0\) を出力します。