시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 0 0 0 0.000%

문제

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

예제 입력 1

2
3 1
2 1
5 3
1 3
4 2
3 1

예제 출력 1

4
2