Сипаттамасы
Ағылшынның бас әріптерінен тұратын ұзындығы $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 шығарыңыз.