P6657 【模板】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$ 的值。 两种方案不同当且仅当存在至少一个棋子所经过的点不同。

无

无

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