זוהי שנת 2075. בזמן ארגון הארכיון שלכם, גיליתם מחדש אוסף של תגים מתחרויות ה-ICPC האזוריות של שנת 2025, שחולקו במקור על ידי ארגון ה-Universal Cup.

ערכת תגים מלאה של UCup.

אולם, בבעיה זו אנו מתייחסים רק לתת-קבוצה של שלושה צבעים.

התגים שלכם מגיעים בשלושה צבעים נבדלים בלבד: אולטרמרין (u), ארגמן (c), ופריווינקל (p). חבילת מזכרות שלמה מוגדרת כארבעה תגים המופיעים בסדר המדויק: אולטרמרין, אחריו ארגמן, אחריו אולטרמרין, ואחריו פריווינקל (ucup).

האוסף שלכם מורכב מ-$4n$ תגים המסודרים בשורה. אתם זוכרים בבירור שבשנת 2025, סידור זה היה אצווה מושלמת:

• ניתן היה לחלק את הרצף ל-$n$ תת-סדרות זרות (כלומר, שימוש בכל תג בתת-סדרה אחת בדיוק), כך שכל תת-סדרה יצרה חבילת מזכרות שלמה (ucup).

עם זאת, במהלך 50 השנים האחרונות, חלק מהתגים דהו, מה שהפך את צבעיהם לבלתי ניתנים להבחנה. מיקומים אלה מיוצגים על ידי ?.

בהינתן המצב הנוכחי של רצף התגים $S$, חשבו את מספר הדרכים לשחזר את הצבעים הדהויים (?) לאחד מבין u, c, או p, כך שהרצף המתקבל יהיה אצווה מושלמת. מאחר שהתשובה עלולה להיות גדולה, הדפיסו אותה מודולו $998\,244\,353$.

שימו לב שניתן לקבל תת-סדרה ממחרוזת על ידי הסרת אפס או יותר תווים מבלי לשנות את סדר התווים הנותרים. לדוגמה, ucp, c ו-ucup הן תת-סדרות של המחרוזת ucup, בעוד ש-uucp אינה תת-סדרה של המחרוזת ucup.

קלט

השורה הראשונה מכילה מספר שלם $n$ ($1 \le n \le 50$).

השורה השנייה מכילה מחרוזת $S$ באורך $4n$ המורכבת מהתווים u, c, p, ו-?.

פלט

הדפיסו את מספר הדרכים להחליף כל ? ב-$S$ באחד מבין u, c, או p, כך שהמחרוזת המתקבלת תייצג אצווה מושלמת, מודולו $998\,244\,353$.

דוגמאות

קלט 1

1
????

פלט 1

1

קלט 2

1
ucup

פלט 2

1

קלט 3

1
uucp

פלט 3

0

קלט 4

1
uu?u

פלט 4

0

קלט 5

2
????????

פלט 5

11

קלט 6

4
u???c???u???p???

פלט 6

437