有一個長度為 $N$ 的字串 $S$，由大寫英文字母組成。你可以對 $S$ 執行任意次數的下列操作：

• 選擇一個整數四元組 $(i, j, k, l)$，滿足 $1 \le i < j < k < l \le |S|$，$S_i = \text{K}$，$S_j = \text{U}$，$S_k = \text{P}$，且 $S_l = \text{C}$。將 $S_i, S_j, S_k, S_l$ 全部替換為 $\text{X}$，並獲得 $(i \times j \times k \times l)$ 日圓。

請找出總共能獲得的最大金額，並對 $998244353$ 取模。

輸入格式

第一行包含一個整數 $N$。$(1 \le N \le 5 \times 10^5)$

第二行包含一個長度為 $N$ 的字串 $S$，由大寫英文字母組成。

輸出格式

輸出答案。

範例

輸入 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。

對於第二個範例，無法執行任何操作，因此輸出 0。