題目描述
俾定一個長度為 $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。