תיאור
נתונה מחרוזת $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.