الوصف
توجد سلسلة نصية $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.