ลำดับของจำนวนเต็ม $V_1, V_2, \dots, V_N$ จะถูกเรียกว่า ลดลงอย่างยิ่งยวด (super decreasing) ถ้า $V_N \ge 0$ และ $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ สำหรับทุก $1 \le i < N$
กำหนดจำนวนเต็มบวก $N$ และ $M$ จงหาจำนวนคู่ของลำดับจำนวนเต็ม $A$ และ $B$ ที่มีความยาว $N$ ซึ่ง $1 \le A_i, B_i \le M$ สำหรับทุก $1 \le i \le N$ และสำหรับทุกลำดับที่ลดลงอย่างยิ่งยวด $V$ ที่มีความยาว $N$ จะสอดคล้องกับ:
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
เนื่องจากจำนวนคู่ดังกล่าวอาจมีค่ามาก จึงให้พิมพ์คำตอบมอดูโล $998\,244\,353$
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะถูกกำหนดให้ในรูปแบบต่อไปนี้:
T N M :
- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- รับประกันว่าผลรวมของ $N$ ในทุกชุดทดสอบไม่เกิน $5000$
- รับประกันว่าผลรวมของ $M$ ในทุกชุดทดสอบไม่เกิน $5000$
ข้อมูลส่งออก
สำหรับแต่ละชุดทดสอบ ให้แสดงจำนวนเต็มหนึ่งตัว คือจำนวนคู่ของลำดับ $(A, B)$ ที่สอดคล้องกับเงื่อนไข มอดูโล $998\,244\,353$
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่าง 1
4 1 1 2 2 2 1 34 43
ข้อมูลส่งออกตัวอย่าง 1
1 10 1 711021868
หมายเหตุ
ชุดทดสอบที่ 1: คู่ของลำดับที่เป็นไปได้เพียงคู่เดียวคือ $([1], [1])$ และเป็นคู่ที่ถูกต้อง
ชุดทดสอบที่ 2: คู่ของลำดับที่ถูกต้องมีดังต่อไปนี้:
- สำหรับ $B = [1, 1]$ การเลือก $A$ ใด ๆ ล้วนถูกต้อง มีทางเลือกที่เป็นไปได้ $4$ แบบ
- สำหรับ $B = [1, 2]$ ทางเลือกของ $A$ ที่ถูกต้องคือ $[1, 2], [2, 1], [2, 2]$
- สำหรับ $B = [2, 1]$ ทางเลือกของ $A$ ที่ถูกต้องคือ $[2, 1], [2, 2]$
- สำหรับ $B = [2, 2]$ ทางเลือกของ $A$ ที่ถูกต้องเพียงแบบเดียวคือ $[2, 2]$
ดังนั้น จำนวนคู่ของลำดับที่ถูกต้องจึงเท่ากับ $4 + 3 + 2 + 1 = 10$