นี่คือปี 2075 ในขณะที่กำลังจัดระเบียบคลังเอกสารของคุณ คุณได้ค้นพบคอลเลกชันเข็มกลัดจากการแข่งขัน ICPC Regional ปี 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