En heltallsfølge $V_1, V_2, \dots, V_N$ kalles superavtakende hvis $V_N \ge 0$ og $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ for alle $1 \le i < N$.
Gitt positive heltall $N$ og $M$, finn antall par av heltallsfølger $A$ og $B$ med lengde $N$ slik at $1 \le A_i, B_i \le M$ for alle $1 \le i \le N$, og slik at det for alle superavtakende følger $V$ med lengde $N$ gjelder at
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Siden antall slike par kan være svært stort, skriv ut svaret modulo $998\,244\,353$.
Inndata
Inndataene er gitt på følgende format:
T N M :
- Alle inndataverdier er heltall.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Det er garantert at summen av $N$ over alle testtilfeller ikke overstiger $5000$.
- Det er garantert at summen av $M$ over alle testtilfeller ikke overstiger $5000$.
Utdata
For hvert testtilfelle, skriv ut ett enkelt heltall — antall par av følger $(A, B)$ som oppfyller betingelsene, modulo $998\,244\,353$.
Eksempler
Eksempelinndata 1
4 1 1 2 2 2 1 34 43
Eksempelutdata 1
1 10 1 711021868
Merk
Testtilfelle 1: Det eneste mulige paret av følger er $([1], [1])$, og det er gyldig.
Testtilfelle 2: Følgende er gyldige par av følger:
- For $B = [1, 1]$ er ethvert valg av $A$ gyldig. Det er $4$ mulige valg.
- For $B = [1, 2]$ er gyldige valg av $A$ lik $[1, 2], [2, 1], [2, 2]$.
- For $B = [2, 1]$ er gyldige valg av $A$ lik $[2, 1], [2, 2]$.
- For $B = [2, 2]$ er det eneste gyldige valget av $A$ lik $[2, 2]$.
Antall gyldige par av følger er altså lik $4 + 3 + 2 + 1 = 10$.