Cho một xâu $S$ có độ dài $N$ bao gồm các chữ cái tiếng Anh viết hoa. Bạn có thể thực hiện thao tác sau trên $S$ bất kỳ số lần nào.

• Chọn một bộ bốn số nguyên $(i, j, k, l)$ sao cho $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$, và $S_l = \text{C}$. Thay thế tất cả $S_i, S_j, S_k, S_l$ bằng $\text{X}$, và nhận được $(i \times j \times k \times l)$ yên.

Tìm số tiền tối đa có thể kiếm được, lấy modulo $998244353$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$ ($1 \le N \le 5 \times 10^5$). Dòng thứ hai chứa một xâu $S$ có độ dài $N$ bao gồm các chữ cái tiếng Anh viết hoa.

Dữ liệu ra

In ra kết quả.

Ví dụ

Dữ liệu vào 1

10
KKUPCUCAPC

Dữ liệu ra 1

1164

Dữ liệu vào 2

4
TUNA

Dữ liệu ra 2

0

Dữ liệu vào 3

30
KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK

Dữ liệu ra 3

619704

Ghi chú

Lưu ý rằng bạn được yêu cầu tìm phần dư của giá trị tối đa, không phải giá trị tối đa của phần dư. Đối với ví dụ đầu tiên, bạn có thể kiếm được 1164 yên bằng cách thực hiện các thao tác sau:

• Chọn $(i, j, k, l) = (1, 3, 4, 7)$. Bạn kiếm được $1 \times 3 \times 4 \times 7 = 84$ yên. Khi đó $S = \text{XKXXCUXAPC}$.
• Chọn $(i, j, k, l) = (2, 6, 9, 10)$. Bạn kiếm được $2 \times 6 \times 9 \times 10 = 1080$ yên. Khi đó $S = \text{XXXXCXXXAXX}$.

Có thể chứng minh rằng không thể kiếm được nhiều hơn 1164 yên, vì vậy in ra 1164. Đối với ví dụ thứ hai, không thể thực hiện thao tác nào dù chỉ một lần, vì vậy in ra 0.