【模板】LGV 引理

题目描述

这是一道模板题。 有一个 $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$ 的值。

输入输出样例

输入样例 #1

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

输出样例 #1

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