סדרת מספרים שלמים $V_1, V_2, \dots, V_N$ נקראת סופר-יורדת אם $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$.