Binary String

시간 제한3초메모리 제한256 MB

요약

각 조건마다 앞 y비트에 1이 정확히 x개 있거나 뒤 x비트에 1이 정확히 y개 있어야 할 때, 길이 n인 이진 문자열의 개수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 누적 합
정답자: 아직 제출이 없습니다

문제

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

예제 1
입력
```
2
3 1
2 1
5 3
1 3
4 2
3 1
```
예상 출력
```
4
2
```