คำอธิบายโจทย์
มีสตริง $S$ ความยาว $N$ ที่ประกอบด้วยตัวอักษรภาษาอังกฤษพิมพ์ใหญ่ คุณสามารถดำเนินการต่อไปนี้กับ $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$) บรรทัดที่สองประกอบด้วยสตริง $S$ ความยาว $N$ ที่ประกอบด้วยตัวอักษรภาษาอังกฤษพิมพ์ใหญ่
ข้อมูลส่งออก
พิมพ์คำตอบออกมา
ตัวอย่าง
ข้อมูลนำเข้า 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