VegiCat gibt dir zwei ganze Zahlen $n$ und $m$. Betrachte ganzzahlige Arrays $a_1, a_2, \ldots, a_n$, sodass
$$ a_1 = 0, \qquad 0 \le a_{i+1} - a_i \le 1 \quad (1 \le i < n). $$
Sei $s_i = a_1 + a_2 + \ldots + a_i$ die Präfixsumme von $a$. VegiCat nennt dir außerdem die Präfixsummen an $m$ Positionen; das heißt, du erhältst $m$ Bedingungen der Form $s_{p_j} = v_j$ ($1 \le j \le m$).
Zähle die Anzahl der Arrays, die alle Bedingungen erfüllen, modulo $998\,244\,353$. Falls kein Array alle Bedingungen erfüllt, ist die Antwort $0$.
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.
Jeder Testfall ist wie folgt gegeben:
Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 100$, $0 \le m \le n$), die Länge des Arrays beziehungsweise die Anzahl der Präfixsummen-Bedingungen.
Die $j$-te der nächsten $m$ Zeilen enthält zwei ganze Zahlen $p_j$ und $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Dies beschreibt eine Bedingung: Die Summe der ersten $p_j$ Elemente des Arrays muss gleich $v_j$ sein.
Die Positionen $p_j$ sind in streng aufsteigender Reihenfolge angegeben.
Ausgabe
Gib für jeden Testfall eine ganze Zahl aus — die Anzahl der gültigen Arrays modulo $998\,244\,353$.
Beispiele
Eingabe 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
Ausgabe 1
1 1 2 2 2 0
Hinweis
Ohne jegliche Präfixbedingungen gibt es genau $2^{n-1}$ solche Arrays, da jede der $n - 1$ benachbarten Differenzen unabhängig voneinander $0$ oder $1$ sein kann.
Im zweiten Testfall ist das einzige Array mit $s_3 = 1$ gleich $(0, 0, 1)$.
Im dritten Testfall erzwingt $s_2 = 0$, dass $a_2 = 0$ gilt, wonach $a_3$ entweder $0$ oder $1$ sein kann.
Im vierten Testfall sind die Arrays $(0, 1, 1, 1)$ und $(0, 0, 1, 2)$.
Im fünften Testfall sind die Arrays mit $s_5 = 4$ gleich $(0, 0, 1, 1, 2)$ und $(0, 1, 1, 1, 1)$.
Im sechsten Testfall erzwingt $s_2 = 0$, dass $a_1 = a_2 = 0$ gilt, also $s_5 \le 6$. Die Bedingung $s_5 = 10$ ist unmöglich.