Eine ganzzahlige Folge $V_1, V_2, \dots, V_N$ heißt superfallend, wenn $V_N \ge 0$ ist und für alle $1 \le i < N$ die Ungleichung $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ gilt.
Gegeben sind positive ganze Zahlen $N$ und $M$. Bestimme die Anzahl der Paare ganzzahliger Folgen $A$ und $B$ der Länge $N$, sodass $1 \le A_i, B_i \le M$ für alle $1 \le i \le N$ gilt und für alle superfallenden Folgen $V$ der Länge $N$
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Da die Anzahl solcher Paare sehr groß sein kann, gib die Antwort modulo $998\,244\,353$ aus.
Eingabe
Die Eingabe erfolgt im folgenden Format:
T N M :
- Alle Eingabewerte sind ganze Zahlen.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Es wird garantiert, dass die Summe von $N$ über alle Testfälle hinweg $5000$ nicht überschreitet.
- Es wird garantiert, dass die Summe von $M$ über alle Testfälle hinweg $5000$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall eine einzige ganze Zahl aus — die Anzahl der Folgenpaare $(A, B)$, die die Bedingungen erfüllen, modulo $998\,244\,353$.
Beispiele
Beispieleingabe 1
4 1 1 2 2 2 1 34 43
Beispielausgabe 1
1 10 1 711021868
Hinweis
Testfall 1: Das einzige mögliche Folgenpaar ist $([1], [1])$, und es ist gültig.
Testfall 2: Die folgenden Folgenpaare sind gültig:
- Für $B = [1, 1]$ ist jede Wahl von $A$ gültig. Es gibt $4$ mögliche Wahlen.
- Für $B = [1, 2]$ sind die gültigen Wahlen für $A$ gleich $[1, 2], [2, 1], [2, 2]$.
- Für $B = [2, 1]$ sind die gültigen Wahlen für $A$ gleich $[2, 1], [2, 2]$.
- Für $B = [2, 2]$ ist die einzige gültige Wahl für $A$ gleich $[2, 2]$.
Somit beträgt die Anzahl der gültigen Folgenpaare $4 + 3 + 2 + 1 = 10$.