คุณได้รับการเรียงสับเปลี่ยน $P$ ของ $\{1, 2, \dots, N\}$
นั่นคือ $P$ เป็นอาร์เรย์ที่มีความยาว $N$ ซึ่งประกอบด้วยจำนวนเต็มทุกจำนวนตั้งแต่ $1$ ถึง $N$ อย่างละหนึ่งตัวพอดี
คุณสามารถดำเนินการต่อไปนี้กับมันได้:
- เลือกดัชนี $i$ ($1 < i < |P|$)
- กำหนดให้ $P_i = \max(P_{i-1}, P_i, P_{i+1})$
- ลบ $P_{i-1}$ และ $P_{i+1}$ ออกจาก $P$ จากนั้นสมาชิกที่เหลือจะถูกจัดลำดับดัชนีใหม่โดยเริ่มตั้งแต่ $1$
การดำเนินการดังกล่าวแต่ละครั้งจะลดความยาวของ $P$ ลง $2$ โดยเฉพาะอย่างยิ่ง หากความยาวของ $P$ เป็น $1$ หรือ $2$ จะไม่สามารถใช้การดำเนินการนี้ได้
จงหาจำนวนของอาร์เรย์ที่แตกต่างกันที่สามารถไปถึงได้โดยการดำเนินการนี้ศูนย์ครั้งหรือมากกว่าโดยเริ่มต้นจาก $P$
เนื่องจากค่านี้มีขนาดใหญ่มาก คุณจึงต้องหาคำตอบในระบบมอดูโล $998\,244\,353$ เท่านั้น
ข้อมูลนำเข้า
ข้อมูลนำเข้ามีรูปแบบดังต่อไปนี้:
T N P_1 P_2 ... P_N ...
ข้อจำกัด
- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le P_i \le N$
- $P_i \ne P_j$ สำหรับทุกๆ $i \ne j$
- รับประกันว่าผลรวมของ $N^2$ ในทุกชุดทดสอบจะไม่เกิน $5000^2$
ข้อมูลส่งออก
สำหรับแต่ละชุดทดสอบ ให้พิมพ์จำนวนเต็มหนึ่งจำนวน — จำนวนของอาร์เรย์ที่แตกต่างกันที่สามารถไปถึงได้โดยการดำเนินการศูนย์ครั้งหรือมากกว่าบน $P$ ในระบบมอดูโล $998\,244\,353$
ตัวอย่าง
ข้อมูลนำเข้า 1
5 2 2 1 3 2 1 3 5 3 1 4 5 2 10 1 2 3 4 5 6 7 8 9 10 15 5 7 6 12 2 13 10 1 11 4 3 9 14 15 8
ข้อมูลส่งออก 1
1 2 5 55 365
หมายเหตุ
ชุดทดสอบที่ 1: ไม่สามารถดำเนินการใดๆ ได้
ชุดทดสอบที่ 2: มีสองความเป็นไปได้:
- ไม่ดำเนินการใดๆ เลย อาร์เรย์สุดท้ายคือ $[2, 1, 3]$
- ดำเนินการหนึ่งครั้งโดยใช้ $i = 2$ อาร์เรย์สุดท้ายคือ $[3]$
สิ่งเหล่านี้คืออาร์เรย์ทั้งหมดที่สามารถไปถึงได้เท่านั้น