En heltalsföljd $V_1, V_2, \dots, V_N$ kallas superavtagande om $V_N \ge 0$ och $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ för alla $1 \le i < N$.
Givet positiva heltal $N$ och $M$, bestäm antalet par av heltalsföljder $A$ och $B$ av längd $N$ sådana att $1 \le A_i, B_i \le M$ för alla $1 \le i \le N$, och det för alla superavtagande följder $V$ av längd $N$ gäller att
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Eftersom antalet sådana par kan vara mycket stort, skriv ut svaret modulo $998\,244\,353$.
Indata
Indatan ges i följande format:
T N M :
- Alla indatavärden är heltal.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Det garanteras att summan av $N$ över alla testfall inte överstiger $5000$.
- Det garanteras att summan av $M$ över alla testfall inte överstiger $5000$.
Utdata
För varje testfall, skriv ut ett enda heltal — antalet par av följder $(A, B)$ som uppfyller villkoren, modulo $998\,244\,353$.
Exempel
Exempelindata 1
4 1 1 2 2 2 1 34 43
Exempelutdata 1
1 10 1 711021868
Förklaring
Testfall 1: Det enda möjliga paret av följder är $([1], [1])$, och det är giltigt.
Testfall 2: Följande är giltiga par av följder:
- För $B = [1, 1]$ är varje val av $A$ giltigt. Det finns $4$ möjliga val.
- För $B = [1, 2]$ är giltiga val av $A$ lika med $[1, 2], [2, 1], [2, 2]$.
- För $B = [2, 1]$ är giltiga val av $A$ lika med $[2, 1], [2, 2]$.
- För $B = [2, 2]$ är det enda giltiga valet av $A$ lika med $[2, 2]$.
Alltså är antalet giltiga par av följder lika med $4 + 3 + 2 + 1 = 10$.