原题链接

题目描述

给定一个数 $n$ 和 $k$ 个区间 $\left[l_i,r_i\right]\subseteq [1,n]$。

我们定义，对于一个长度为 $n$ 的，仅由 ( 和 ) 组成的合法括号序列，如果它的每一个区间 $\left[l_i,r_i\right]$ 内的子串都是合法括号序列，那么这个括号序列是严格合法的。

求严格合法的括号序列的数量，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $t\ (1\le t\le 10^5)$，表示数据组数。

对于每组数据，第一行两个整数 $n,k\ (1\le n\le 3\times 10^5,0\le k\le3\times 10^5)$，表示严格合法括号序列的长度和给定区间的个数。

接下来 $k$ 行，每行两个整数 $l_i,r_i(1\le l_i\le r_i\le n)$。

保证单个测试店内 $n$ 与 $k$ 的和不超过 $3\times 10^5$。

输出格式

对于每组数据，输出一行一个整数表示严格合法括号序列的个数对 $998244353$ 取模后的结果。

7
6 0
5 0
8 1
1 3
10 2
3 4
6 9
1000 3
100 701
200 801
300 901
28 5
1 12
3 20
11 14
4 9
18 19
4 3
1 4
1 4
1 4

5
0
0
4
839415253
140
2

说明/提示

• 对于第一组数据，长度为 $6$ 的 $5$ 个严格合法括号序列是：((()))、(()())、(())()、()(()) 和 ()()()()。
• 对于第二组数据，没有长度为 $5$ 的合法括号序列，所以没有长度为 $5$ 的严格合法括号序列。
• 对于第三组数据，没有长度为 $8$ 且子串 $[1\cdots3]$ 是合法括号序列的严格合法括号序列。
• 对于第四组数据，$4$ 个严格合法括号序列如下：((())(()))、((())()())、()()((())) 和 ()()(()())。