VegiCat antaa sinulle kaksi kokonaislukua $n$ ja $m$. Tarkastellaan kokonaislukutaulukoita $a_1, a_2, \ldots, a_n$, joille pätee
$$ a_1 = 0, \qquad 0 \le a_{i+1} - a_i \le 1 \quad (1 \le i < n). $$
Olkoon $s_i = a_1 + a_2 + \ldots + a_i$ taulukon $a$ etuliitesumma. VegiCat kertoo sinulle myös etuliitesummat $m$ kohdassa; toisin sanoen sinulle annetaan $m$ muotoa $s_{p_j} = v_j$ ($1 \le j \le m$) olevaa rajoitetta.
Laske kaikkien rajoitteiden mukaiset taulukot modulo $998\,244\,353$. Jos mikään taulukko ei toteuta kaikkia rajoitteita, vastaus on $0$.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.
Jokainen testitapaus annetaan seuraavasti:
Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 100$, $0 \le m \le n$), taulukon pituuden ja etuliitesummarajoitteiden lukumäärän.
Seuraavista $m$ rivistä $j$:s sisältää kaksi kokonaislukua $p_j$ ja $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Tämä kuvaa rajoitteen: taulukon ensimmäisen $p_j$ alkion summan on oltava yhtä suuri kuin $v_j$.
Kohdat $p_j$ annetaan aidosti kasvavassa järjestyksessä.
Tuloste
Tulosta jokaiselle testitapaukselle kokonaisluku — kelvollisten taulukoiden lukumäärä modulo $998\,244\,353$.
Esimerkit
Syöte 1
6 1 0 3 1 3 1 3 1 2 0 4 1 4 3 5 2 1 0 5 4 5 2 2 0 5 10
Tuloste 1
1 1 2 2 2 0
Huomautus
Ilman mitään etuliiterajoitteita tällaisia taulukoita on täsmälleen $2^{n-1}$, koska jokainen $n - 1$ vierekkäisestä erotuksesta voi toisistaan riippumatta olla $0$ tai $1$.
Toisessa testitapauksessa ainoa taulukko, jolla $s_3 = 1$, on $(0, 0, 1)$.
Kolmannessa testitapauksessa $s_2 = 0$ pakottaa $a_2 = 0$, minkä jälkeen $a_3$ voi olla $0$ tai $1$.
Neljännessä testitapauksessa taulukot ovat $(0, 1, 1, 1)$ ja $(0, 0, 1, 2)$.
Viidennessä testitapauksessa taulukot, joilla $s_5 = 4$, ovat $(0, 0, 1, 1, 2)$ ja $(0, 1, 1, 1, 1)$.
Kuudennessa testitapauksessa $s_2 = 0$ pakottaa $a_1 = a_2 = 0$, joten $s_5 \le 6$. Rajoite $s_5 = 10$ on mahdoton.