Kokonaislukujonoa $V_1, V_2, \dots, V_N$ kutsutaan superväheneväksi, jos $V_N \ge 0$ ja $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ kaikilla $1 \le i < N$.
Annettuna ovat positiiviset kokonaisluvut $N$ ja $M$. Etsi sellaisten pituutta $N$ olevien kokonaislukujonojen $A$ ja $B$ parien lukumäärä, joille $1 \le A_i, B_i \le M$ kaikilla $1 \le i \le N$ ja kaikille pituutta $N$ oleville superväheneville jonoille $V$ pätee
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Koska tällaisten parien lukumäärä voi olla hyvin suuri, tulosta vastaus modulo $998\,244\,353$.
Syöte
Syöte annetaan seuraavassa muodossa:
T N M :
- Kaikki syötteen arvot ovat kokonaislukuja.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- On taattu, että lukujen $N$ summa yli kaikkien testitapausten ei ylitä arvoa $5000$.
- On taattu, että lukujen $M$ summa yli kaikkien testitapausten ei ylitä arvoa $5000$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi kokonaisluku — ehdot täyttävien jonoparien $(A, B)$ lukumäärä modulo $998\,244\,353$.
Esimerkit
Esimerkkisyöte 1
4 1 1 2 2 2 1 34 43
Esimerkkituloste 1
1 10 1 711021868
Huomautus
Testitapaus 1: Ainoa mahdollinen jonopari on $([1], [1])$, ja se on kelvollinen.
Testitapaus 2: Seuraavat jonoparit ovat kelvollisia:
- Kun $B = [1, 1]$, mikä tahansa jonon $A$ valinta on kelvollinen. Mahdollisia valintoja on $4$.
- Kun $B = [1, 2]$, kelvolliset jonon $A$ valinnat ovat $[1, 2], [2, 1], [2, 2]$.
- Kun $B = [2, 1]$, kelvolliset jonon $A$ valinnat ovat $[2, 1], [2, 2]$.
- Kun $B = [2, 2]$, ainoa kelvollinen jonon $A$ valinta on $[2, 2]$.
Siispä kelvollisten jonoparien lukumäärä on $4 + 3 + 2 + 1 = 10$.