Une séquence d'entiers $V_1, V_2, \dots, V_N$ est dite super décroissante si $V_N \ge 0$ et $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ pour tout $1 \le i < N$.
Étant donnés deux entiers strictement positifs $N$ et $M$, trouvez le nombre de couples de séquences d'entiers $A$ et $B$ de longueur $N$ tels que $1 \le A_i, B_i \le M$ pour tout $1 \le i \le N$, et que pour toute séquence super décroissante $V$ de longueur $N$,
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Comme le nombre de tels couples peut être très grand, affichez la réponse modulo $998\,244\,353$.
Entrée
L'entrée est donnée dans le format suivant :
T N M :
- Toutes les valeurs d'entrée sont des entiers.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Il est garanti que la somme de $N$ sur l'ensemble des cas de test ne dépasse pas $5000$.
- Il est garanti que la somme de $M$ sur l'ensemble des cas de test ne dépasse pas $5000$.
Sortie
Pour chaque cas de test, affichez un seul entier — le nombre de couples de séquences $(A, B)$ satisfaisant les conditions, modulo $998\,244\,353$.
Exemples
Exemple d'entrée 1
4 1 1 2 2 2 1 34 43
Exemple de sortie 1
1 10 1 711021868
Note
Cas de test 1 : Le seul couple de séquences possible est $([1], [1])$, et il est valide.
Cas de test 2 : Voici les couples de séquences valides :
- Pour $B = [1, 1]$, n'importe quel choix de $A$ est valide. Il y a $4$ choix possibles.
- Pour $B = [1, 2]$, les choix valides de $A$ sont $[1, 2], [2, 1], [2, 2]$.
- Pour $B = [2, 1]$, les choix valides de $A$ sont $[2, 1], [2, 2]$.
- Pour $B = [2, 2]$, le seul choix valide de $A$ est $[2, 2]$.
Ainsi, le nombre de couples de séquences valides est égal à $4 + 3 + 2 + 1 = 10$.