19318번 - Binary String 다국어

문제

Rikka has a binary string with $n$ bits.

We don't know the string. The thing we know for sure is, for each $i \in \{1, 2, \ldots, m\},ドル at least one of the following is true: "there are exactly $x_i$ ones in the first $y_i$ bits" or "there are exactly $y_i$ ones in the last $x_i$ bits".

Find the number of possible binary strings modulo 998ドル,244円,353円$.

입력

The first line contains an integer $T$ which denotes the number of test cases (1ドル \leq T \leq 5$).

For each test case, the first line contains two integers $n$ and $m$ (1ドル \leq n \leq 5000,ドル 0ドル \leq m \leq 1000$).

The $i$-th of the following $m$ lines contains two integers $x_i$ and $y_i$ (0ドル \leq x_i, y_i \leq n,ドル $x_i \neq 0$ or $y_i \neq 0$).

출력

For each test case, print an integer which denotes the number of binary strings satisfying the constraints, modulo 998ドル,244円,353円$.

제한

힌트