Yana, Mino, White และ Huzz เป็นเพื่อนสนิทกัน
หลังจากทำภารกิจอันหนักหน่วงของโค้ชเสร็จสิ้นในที่สุด Huzz ก็ได้เวลาพักผ่อน เขาค้นพบมันในบ่ายวันหนึ่งที่แสนขี้เกียจ วันที่โลกดูเหมือนจะหมุนช้าลง โอบล้อมด้วยไออุ่นสีทองของยามพลบค่ำที่กำลังคืบคลานเข้ามา สายลมอ่อนๆ ทำได้เพียงพัดพาละอองฝุ่นให้เริงระบำอยู่ในลำแสงอาทิตย์ที่ส่องลอดผ่านใบของต้นโอ๊กใหญ่
ในความว่างเปล่าอันแสนสบายและชวนง่วงเหงานั้น Huzz ได้พบการเรียงสับเปลี่ยนอันหนึ่งในตุ๊กตาฉลามนุ่มนิ่มของเขา เขาจึงตัดสินใจแบ่งปันมันกับเพื่อนๆ เพื่อความสนุกสนาน
Mino ชอบการแบ่ง เขาสามารถแบ่งการเรียงสับเปลี่ยนนี้ออกเป็นหลายช่วงที่ติดกันได้
Yana ชอบการสลับ เขาสามารถเลือกหนึ่งช่วงที่ติดกันแล้วสลับสมาชิกที่มีค่ามากที่สุดกับสมาชิกที่มีค่าน้อยที่สุดในช่วงนั้นได้
กล่าวโดยเจาะจงคือ พวกเขาสามารถดำเนินการสองประเภทต่อไปนี้กี่ครั้งก็ได้ ในลำดับใดก็ได้:
- split: เลือกหนึ่งช่วงที่ติดกันที่มีความยาวมากกว่า $1$ จากนั้นเลือกตำแหน่งหนึ่งภายในช่วงนั้นแล้วแบ่งออกเป็นสองช่วงที่ติดกันซึ่งอยู่ถัดกัน ตัวอย่างเช่น $(a_i, \dots, a_j)$ สามารถแบ่งออกเป็น $(a_i, \dots, a_k)$ และ $(a_{k+1}, \dots, a_j)$ โดยที่ $i \le k < j$
- swap: เลือกหนึ่งช่วงที่ติดกันแล้วสลับสมาชิกที่มีค่ามากที่สุดกับสมาชิกที่มีค่าน้อยที่สุดของช่วงนั้น
หลังจากดำเนินการไปจำนวนหนึ่ง พวกเขาจะหยุดดำเนินการ และนำช่วงทั้งหมดที่ได้มารวมกันตามลำดับเดิมเพื่อสร้างการเรียงสับเปลี่ยนใหม่
White ชอบการนับ เธอสงสัยว่า — พวกเขาจะสามารถได้การเรียงสับเปลี่ยนที่แตกต่างกันทั้งหมดกี่แบบ?
เนื่องจากผลลัพธ์อาจมีค่าใหญ่มาก คุณจึงเพียงแค่ต้องหาคำตอบมอดูโล $998\,244\,353$
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 500$) แทนความยาวของการเรียงสับเปลี่ยน
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$) แทนตัวการเรียงสับเปลี่ยนนั้น รับประกันว่า $\{a_n\}$ เป็นการเรียงสับเปลี่ยน
ข้อมูลส่งออก
พิมพ์จำนวนเต็มหนึ่งจำนวน คือจำนวนการเรียงสับเปลี่ยนที่แตกต่างกันที่พวกเขาสามารถได้รับ มอดูโล $998\,244\,353$
ตัวอย่าง
ข้อมูลนำเข้า
4 1 4 2 3
ข้อมูลส่งออก
10
ข้อมูลนำเข้า
7 5 1 4 2 6 3 7
ข้อมูลส่งออก
340
หมายเหตุ
ในตัวอย่างแรก ต่อไปนี้คือการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดที่พวกเขาสามารถได้รับ:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$