Deskripsi
Terdapat sebuah string $S$ sepanjang $N$ yang terdiri dari huruf alfabet Inggris kapital. Anda dapat melakukan operasi berikut pada $S$ berapa kali pun:
- Pilih sebuah kuadrupel bilangan bulat $(i, j, k, l)$ sedemikian sehingga $1 \le i < j < k < l \le |S|$, $S_i = \text{K}$, $S_j = \text{U}$, $S_k = \text{P}$, dan $S_l = \text{C}$. Ganti semua $S_i, S_j, S_k, S_l$ dengan $\text{X}$, dan dapatkan $(i \times j \times k \times l)$ yen.
Carilah jumlah uang maksimum yang dapat diperoleh secara keseluruhan, modulo $998244353$.
Masukan
Baris pertama berisi sebuah bilangan bulat $N$ ($1 \le N \le 5 \times 10^5$). Baris kedua berisi sebuah string $S$ sepanjang $N$ yang terdiri dari huruf alfabet Inggris kapital.
Keluaran
Cetak jawabannya.
Contoh
Masukan 1
10 KKUPCUCAPC
Keluaran 1
1164
Masukan 2
4 TUNA
Keluaran 2
0
Masukan 3
30 KUCCKCKKPUKUPCUCPUCKPCKKUUPCPK
Keluaran 3
619704
Catatan
Perhatikan bahwa yang diminta adalah sisa bagi dari nilai maksimum, bukan nilai maksimum dari sisa bagi. Untuk contoh pertama, Anda dapat memperoleh 1164 yen dengan melakukan operasi berikut:
- Pilih $(i, j, k, l) = (1, 3, 4, 7)$. Anda memperoleh $1 \times 3 \times 4 \times 7 = 84$ yen. Kemudian $S = \text{XKXXCUXAPC}$.
- Pilih $(i, j, k, l) = (2, 6, 9, 10)$. Anda memperoleh $2 \times 6 \times 9 \times 10 = 1080$ yen. Kemudian $S = \text{XXXXCXXXAXX}$.
Dapat dibuktikan bahwa tidak mungkin memperoleh lebih dari 1164 yen, jadi cetak 1164. Untuk contoh kedua, tidak ada operasi yang dapat dilakukan bahkan satu kali pun, jadi cetak 0.