seuOJ492 - 大兴土木

题目描述

DDL战神小G闪耀登场。

DDL战神小G接了一个项目，需要设计一条商业街上大楼的高度，设这一条街上大楼的高度依次为 h1,h2,...,hnh_1,h_2,...,h_n ，要求满足这是一个 1,...,n1,...,n 的排列。

既然是项目，甲方必然会有一些奇奇怪怪的要求，总之，甲方一共提出了 mm 个要求，每个要求给出了两个数 ll 和 rr ，表示一个区间，甲方要求对于在这个区间里的所有楼的高度都要小于等于两边大楼中的最高楼的高度，即对于 ∀i∈[l,r]\forall i\in[l,r]， hi≤max⁡{hl,hr}h_i\leq\max\{h_l,h_r\} 。

由于DDL将近的原因，小G需要你帮他计算出满足甲方所有要求的方案数，这样他才好分配时间。

但拖DDL不是一个好习惯，为了给小G一个教训，你只需要回答他方案数对 998244353998244353 取模的结果。

输入格式

第一行，一个整数 t(1≤t≤10)t(1\le t\le 10) ，代表数据组数。

对于每组数据：
第一行输入两个整数 n,m(1≤n≤500;0≤m≤n2)n,m(1\le n \le 500;0\le m \le n^2) ，代表大楼个数和要求个数。
第 22 到 m+1m+1 行分别输入两个整数 l,r(1≤l≤r≤n)l,r(1\le l\le r\le n) ，代表对应要求的区间。

保证同一测试点内 nn 的总和不超过 500500。

输出格式

输出满足所有要求的方案数，答案对 998244353998244353 取模。

样例

输入样例

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

输出样例

4
144
36