给你一个整数 $$$n$$$ 和 $$$k$$$ 间隔。第 $$$i$$$ 间隔为 $$$[l_i,r_i]$$$,其中 $$$1 \leq l_i \leq r_i \leq n$$$。
让我们称长度为$$$n$$$的正则括号序列$$$^{\dagger,\ddagger}$$$为超正则,如果对于每个$$$i$$$使得$$$1 \leq i \leq k$$$,子串$$$\overline{s_{l_i} s_{l_{i}+1} \ldots s_{r_i}}$$$ 也是一个常规的括号序列。
你的任务是计算超正则括号序列的数量。由于这个数字可能非常大,因此您只需对 $$$998\,244\,353$$$ 求模即可。
$$$^\dagger$$$ 括号序列是仅包含字符“(”和“)”的字符串。
$$$^\ddagger$$$ 如果可以通过添加字符 + 和 1 将括号序列转换为有效的数学表达式,则该括号序列称为正则。例如,序列 (())()、()、(()(())) 和空字符串是正则,而 )(、(() 和 (()))( 则不是正则。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$0 \le k \le 3 \cdot 10^5$$$) — 分别是超正则括号序列的长度和间隔的数量。
每个测试用例的以下 $$$k$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l \le r \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$,所有测试用例的 $$$k$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出以 $$$998\,244\,353$$$ 为模的超正则括号序列的数量。
示例
输入 #1
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
输出 #1
5 0 0 4 839415253 140 2
注意
- 对于第一个测试用例,长度为 $$$6$$$ 的 $$$5$$$ 超正则括号字符串为:((()))、(()())、(())()、()(()) 和 ()()()。
- 对于第二个测试用例,没有长度为 $$$5$$$ 的常规括号字符串,因此,也没有长度为 $$$5$$$ 的超正则括号字符串。
- 对于第三个测试用例,不存在长度为 $$$8$$$ 的超正则括号字符串,其中子字符串 $$$[1 \ldots 3]$$$ 是常规括号字符串。
- 对于第四个测试用例,$$$4$$$ 超正则括号字符串为: ((())(()))、((())()())、()()((())) 和 ()()(()())