英大文字からなる長さ $N$ の文字列 $S$ が与えられます。あなたは $S$ に対して以下の操作を何度でも行うことができます。

• $1 \le i < j < k < l \le |S|$ かつ $S_i = \text{'K'}, S_j = \text{'U'}, S_k = \text{'P'}, S_l = \text{'C'}$ を満たす整数の組 $(i, j, k, l)$ を選びます。$S_i, S_j, S_k, S_l$ をすべて $\text{'X'}$ に置き換え、$i \times j \times k \times l$ 円を獲得します。

合計で獲得できる金額の最大値を $998244353$ で割った余りを求めてください。

入力

入力は以下の形式で与えられます。

$N$ $S$

• $1 \le N \le 5 \times 10^5$
• $S$ は長さ $N$ の英大文字からなる文字列です。

出力

答えを出力してください。

入出力例

入力 1

10
KKUPCUCAPC

出力 1

1164

入力 2

4
TUNA

出力 2

0

入力 3

30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK

出力 3

619704

注記

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

最初の例では、以下の操作を行うことで 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番目の例では、操作を一度も行うことができないため、0 を出力します。