대문자 영어 알파벳으로 이루어진 길이 $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$이 주어진다. ($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을 출력한다.