نحن في عام 2075. أثناء تنظيم أرشيفك، أعدت اكتشاف مجموعة من الشارات من مسابقات ICPC الإقليمية لعام 2025، والتي وزعتها في الأصل منظمة Universal Cup.

مجموعة كاملة من شارات UCup.

ومع ذلك، في هذه المسألة، نأخذ في الاعتبار فقط مجموعة جزئية من ثلاثة ألوان.

تأتي شاراتك بثلاثة ألوان مميزة فقط: الأزرق اللازوردي (u)، والقرمزي (c)، والأزرق العناقي (p). تُعرَّف حزمة التذكارات الكاملة بأنها أربع شارات تظهر بالترتيب الدقيق التالي: أزرق لازوردي، ثم قرمزي، ثم أزرق لازوردي، ثم أزرق عناقي (ucup).

تتكون مجموعتك من $4n$ شارة مرتبة في صف واحد. تتذكر بوضوح أنه في عام 2025، كان هذا الترتيب يمثل دفعة مثالية:

• يمكن تقسيم المتتالية إلى $n$ متتاليات جزئية منفصلة (أي استخدام كل شارة في متتالية جزئية واحدة بالضبط)، بحيث تشكل كل متتالية جزئية حزمة تذكارات كاملة (ucup).

ومع ذلك، على مدار الخمسين عاماً الماضية، بهتت بعض الشارات، مما جعل ألوانها غير قابلة للتمييز. يُشار إلى هذه المواضع بالرمز ?.

بالنظر إلى الحالة الحالية لمتتالية الشارات $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