Ciąg liczb całkowitych $V_1, V_2, \dots, V_N$ nazywamy supermalejącym, jeśli $V_N \ge 0$ oraz $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ dla wszystkich $1 \le i < N$.
Mając dane dodatnie liczby całkowite $N$ oraz $M$, wyznacz liczbę par ciągów liczb całkowitych $A$ i $B$ o długości $N$, takich że $1 \le A_i, B_i \le M$ dla wszystkich $1 \le i \le N$ oraz dla wszystkich supermalejących ciągów $V$ o długości $N$ zachodzi:
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Ponieważ liczba takich par może być bardzo duża, wypisz odpowiedź modulo $998\,244\,353$.
Wejście
Wejście jest podawane w następującym formacie:
T N M :
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Gwarantuje się, że suma $N$ po wszystkich przypadkach testowych nie przekracza $5000$.
- Gwarantuje się, że suma $M$ po wszystkich przypadkach testowych nie przekracza $5000$.
Wyjście
Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — liczbę par ciągów $(A, B)$ spełniających warunki, modulo $998\,244\,353$.
Przykłady
Przykładowe wejście 1
4 1 1 2 2 2 1 34 43
Przykładowe wyjście 1
1 10 1 711021868
Uwaga
Przypadek testowy 1: Jedyną możliwą parą ciągów jest $([1], [1])$ i jest ona poprawna.
Przypadek testowy 2: Poniżej przedstawiono poprawne pary ciągów:
- Dla $B = [1, 1]$ każdy wybór $A$ jest poprawny. Istnieją $4$ możliwe wybory.
- Dla $B = [1, 2]$ poprawne wybory $A$ to $[1, 2], [2, 1], [2, 2]$.
- Dla $B = [2, 1]$ poprawne wybory $A$ to $[2, 1], [2, 2]$.
- Dla $B = [2, 2]$ jedynym poprawnym wyborem $A$ jest $[2, 2]$.
Zatem liczba poprawnych par ciągów wynosi $4 + 3 + 2 + 1 = 10$.