Una sequenza di interi $V_1, V_2, \dots, V_N$ è detta super decrescente se $V_N \ge 0$ e $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ per tutti gli $1 \le i < N$.
Dati gli interi positivi $N$ e $M$, trova il numero di coppie di sequenze di interi $A$ e $B$ di lunghezza $N$ tali che $1 \le A_i, B_i \le M$ per tutti gli $1 \le i \le N$, e per tutte le sequenze super decrescenti $V$ di lunghezza $N$,
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Poiché il numero di tali coppie può essere molto grande, stampa la risposta modulo $998\,244\,353$.
Input
L'input è fornito nel seguente formato:
T N M :
- Tutti i valori di input sono interi.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- È garantito che la somma di $N$ su tutti i casi di test non supera $5000$.
- È garantito che la somma di $M$ su tutti i casi di test non supera $5000$.
Output
Per ogni caso di test, stampa un singolo intero — il numero di coppie di sequenze $(A, B)$ che soddisfano le condizioni, modulo $998\,244\,353$.
Esempi
Input di esempio 1
4 1 1 2 2 2 1 34 43
Output di esempio 1
1 10 1 711021868
Nota
Caso di test 1: L'unica coppia possibile di sequenze è $([1], [1])$, ed è valida.
Caso di test 2: Le seguenti sono coppie valide di sequenze:
- Per $B = [1, 1]$, qualsiasi scelta di $A$ è valida. Ci sono $4$ scelte possibili.
- Per $B = [1, 2]$, le scelte valide di $A$ sono $[1, 2], [2, 1], [2, 2]$.
- Per $B = [2, 1]$, le scelte valide di $A$ sono $[2, 1], [2, 2]$.
- Per $B = [2, 2]$, l'unica scelta valida di $A$ è $[2, 2]$.
Quindi, il numero di coppie valide di sequenze è uguale a $4 + 3 + 2 + 1 = 10$.