시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
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$.
2 3 1 2 1 5 3 1 3 4 2 3 1
4 2