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$.