ให้ $B$ เป็นอาร์เรย์ความยาว $M$ ที่ประกอบด้วยจำนวนเต็มบวก
ในการดำเนินการหนึ่งครั้ง คุณสามารถเลือกลำดับย่อยที่ไม่ว่าง$^\dagger$ ของดัชนี $1 \le i_1 < i_2 < \dots < i_k \le M$ ที่ทำให้ค่า $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ แตกต่างกันเป็นคู่ ๆ แล้วลดค่าที่เลือกแต่ละตัวลง $1$
นิยาม คะแนน ของ $B$ ซึ่งเขียนแทนด้วย $\text{score}(B)$ ให้เป็นจำนวนครั้งของการดำเนินการที่น้อยที่สุดที่ต้องใช้เพื่อทำให้สมาชิกทุกตัวของ $B$ มีค่าเท่ากับ $0$
คุณได้รับอาร์เรย์ $A$ ที่มีความยาว $N$
จงหาผลรวมของคะแนนของลำดับย่อยที่ไม่ว่างทั้งหมดของ $A$
เนื่องจากค่าที่ได้อาจมีค่ามาก ให้แสดงผลลัพธ์มอดูโล $998\,244\,353$
$^\dagger$ ลำดับ $C$ จะถูกเรียกว่าลำดับย่อยของลำดับ $D$ หากสามารถได้มาจาก $D$ โดยการลบสมาชิกบางตัวออก (อาจไม่ลบเลยหรือลบทั้งหมดก็ได้) โดยไม่เปลี่ยนลำดับของสมาชิกที่เหลืออยู่
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะถูกกำหนดให้ในรูปแบบต่อไปนี้:
T N A_1 A_2 ... A_N :
- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $1 \le T \le 10^5$
- $1 \le N \le 5000$
- $1 \le A_i \le 10^9$
- รับประกันว่าผลรวมของ $N^2$ ในทุกชุดทดสอบไม่เกิน $5000^2$
ข้อมูลส่งออก
สำหรับแต่ละชุดทดสอบ ให้แสดงจำนวนเต็มหนึ่งตัว — ผลรวมของคะแนนของลำดับย่อยที่ไม่ว่างทั้งหมดของ $A$ มอดูโล $998\,244\,353$
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่าง 1
3 1 5 3 1 1 3 4 2 2 2 2
ข้อมูลส่งออกตัวอย่าง 1
5 16 47
หมายเหตุ
ชุดทดสอบที่ 1: ลำดับย่อยที่ไม่ว่างเพียงหนึ่งเดียวคือ $[5]$ ซึ่งมีคะแนนเป็น $5$ ดังนั้นคำตอบคือ $5$
ชุดทดสอบที่ 2: ลำดับย่อยที่ไม่ว่างของ $[1, 1, 3]$ ได้แก่:
- ลำดับย่อยที่เท่ากับ $[1]$ สองลำดับ แต่ละลำดับมีคะแนน $1$
- $[3]$ มีคะแนน $3$
- $[1, 1]$ มีคะแนน $2$
- ลำดับย่อยที่เท่ากับ $[1, 3]$ สองลำดับ แต่ละลำดับมีคะแนน $3$
- $[1, 1, 3]$ มีคะแนน $3$
ดังนั้น ผลรวมทั้งหมดคือ $16$