กำหนดการเรียงสับเปลี่ยน $p$ ที่มีความยาว $n$

ในแต่ละการดำเนินการ จะสุ่มเลือกจำนวนเต็ม $i$ ด้วยความน่าจะเป็นที่เท่ากัน ($1 \le i \le n$) จากนั้นทำการเรียงลำดับช่วงอุปสรรค (prefix) $[1, i]$ และช่วงปัจจัย (suffix) $[i + 1, n]$ ของการเรียงสับเปลี่ยน $p$ จากน้อยไปมากตามลำดับ โดยเฉพาะอย่างยิ่ง เมื่อ $i = n$ ช่วงปัจจัยจะว่างเปล่า ซึ่งเทียบเท่ากับการเรียงลำดับทั้งการเรียงสับเปลี่ยน

คุณต้องหาค่าคาดหมายของจำนวนการดำเนินการที่ต้องใช้จนกว่าการเรียงสับเปลี่ยนสุดท้ายจะเรียงลำดับจากน้อยไปมากอย่างสมบูรณ์ (นั่นคือ $p_j = j$)

คำตอบต้องนำมาหาเศษเหลือด้วย $998\,244\,353$

ข้อมูลนำเข้า

โจทย์ข้อนี้มีหลายชุดข้อมูลทดสอบ

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 100$) แทนจำนวนชุดข้อมูลทดสอบ

สำหรับแต่ละชุดข้อมูลทดสอบ:

• บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 500$) แทนความยาวของการเรียงสับเปลี่ยน
• บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$) แทนการเรียงสับเปลี่ยน $p$ ที่กำหนด รับประกันว่าลำดับที่กำหนดให้เป็นการเรียงสับเปลี่ยนของ $1 \sim n$

รับประกันว่าผลรวมของ $n$ ในทุกชุดข้อมูลทดสอบไม่เกิน $2000$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็มหนึ่งจำนวน คือค่าคาดหมายของจำนวนการดำเนินการมอดูโล $998\,244\,353$

ตัวอย่าง

ข้อมูลนำเข้า

3
3
3 1 2
2
2 1
5
3 2 5 1 4

ข้อมูลส่งออก

748683267
2
670695427