给定一个长度为 $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。