#P12399. [2025年联测]分

    ID: 11549 传统题 2000ms 512MiB 尝试: 9 已通过: 1 难度: 6 上传者: 标签>CF2100组合数学枚举数学构造前缀和

[2025年联测]分

题目描述

一个长度为 nn 的序列,每个位置为 00 或 11 两种。现在给出 mm 个限制条件,第 ii 个限制条件给出 xix_i 、yiy_i ,要求至少满足以下两个条件之一:

  • 序列的前 xix_i 个位置中,恰好有 yiy_i 个 11 ;
  • 序列的后 yiy_i 个位置中,恰好有 xix_i 个 11 ;

求有多少个序列满足所有限制条件。答案可能很大,只需要输出它对 998244353998244353 取模后的结果即可。

输入

第一行:一个整数 TT ,表示数据组数。

对于每组数据:

第一行:两个整数 nn 、mm ,含义如题目所述;
接下来的 mm 行,每行两个整数 xix_i 、yiy_i ,描述第 ii 个限制条件 ,含义如题目所述。

输出

对于每组数据输出一行一个整数,表示方案数模 998244353998244353 的结果。

样例

样例输入

2
3 1
2 1
5 3
1 3
4 2
3 1

样例输出

4
2

数据范围与提示

对于 20%20\% 的数据,n,m≤20n,m\le 20 ;
对于 40%40\% 的数据,n≤20n\le 20 ;
对于 60%60\% 的数据,n≤60n\le 60 ;
对于另外 20%20\% 的数据,保证 xi<yix_i<y_i ;
对于 100%100\% 的数据,1≤T≤51\le T\le 5 ,1≤n≤50001\le n\le 5000 ,1≤m≤10001\le m\le 1000 ,0≤xi,yi≤n0\le x_i,y_i\le n 。