Description

This is a template problem.

There is an $n\times n$ chessboard, with the bottom-left corner at $(1,1)$ and the top-right corner at $(n,n)$. If a piece is at $(x,y)$, then in one step it can only move to $(x+1,y)$ or $(x,y+1)$.

Now there are $m$ pieces. The $i$-th piece starts at $(a_i,1)$ and must finally move to $(b_i,n)$. Ask how many valid plans there are such that every piece can move from its start to its end, and for all pieces, the points on their paths are pairwise disjoint. Output the number of plans modulo $998244353$.

Two plans are different if and only if there exists at least one piece whose visited points are different.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, representing the number of test cases in this testdata.

For each test case:

The first line contains two integers $n,m$, representing the size of the board and the number of start/end pairs.

The next $m$ lines each contain $2$ integers $a_i,b_i$, whose meaning has been explained in the description.

Output Format

For each test case, output one line containing one integer, representing the number of plans modulo $998244353$.

3
3 2
1 2
2 3
5 2
1 3
3 5
10 5
3 5
4 7
5 8
7 9
9 10

3
155
2047320

Hint

• For $30\%$ of the testdata, $n\leq 100$, $m\leq 8$.

• For $100\%$ of the testdata, $T\leq5$, $2\leq n\leq10^6$, $1\leq m\leq100$, $1\leq a_1\leq a_2\leq \dots\leq a_m\leq n$, $1\leq b_1\leq b_2\leq \dots\leq b_m\leq n$.

Translated by ChatGPT 5