题目描述

这是一道模板题。

有一个 $n\times n$ 的棋盘，左下角为 $(1,1)$，右上角为 $(n,n)$，若一个棋子在点 $(x,y)$，那么走一步只能走到 $(x+1,y)$ 或 $(x,y+1)$。

现在有 $m$ 个棋子，第 $i$ 个棋子一开始放在 $(a_i,1)$，最终要走到 $(b_i,n)$。问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过路径上的点互不相交。输出方案数 $\bmod\ 998244353$ 的值。

两种方案不同当且仅当存在至少一个棋子所经过的点不同。

输入格式

本题有多组数据

第一行一个整数 $T$，表示该测试点的数据组数。

对于每组数据：

第一行两个整数 $n,m$，分别表示棋盘的大小和起点终点的数量。

接下来 $m$ 行，每行 $2$ 个整数 $a_i,b_i$，其意义已在题目描述中说明。

输出格式

对于每一组数据，输出一行一个整数表示方案数 $\bmod\ 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

提示

• 对于 $30\%$ 的数据，$n\leq 100$，$m\leq 8$。

• 对于 $100\%$ 的数据，$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$。