CF1830C.Hyperregular Bracket Strings

You are given an integer $n$ and $k$ intervals. The $i$-th interval is $[l_i,r_i]$ where $1 \leq l_i \leq r_i \leq n$.

Let us call a regular bracket sequence$^{\dagger,\ddagger}$ of length $n$ hyperregular if for each $i$ such that $1 \leq i \leq k$, the substring $\overline{s_{l_i} s_{l_{i}+1} \ldots s_{r_i}}$ is also a regular bracket sequence.

Your task is to count the number of hyperregular bracket sequences. Since this number can be really large, you are only required to find it modulo $998\,244\,353$.

$^\dagger$ A bracket sequence is a string containing only the characters "(" and ")".

$^\ddagger$ A bracket sequence is called regular if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are regular, while )(, ((), and (()))( are not.

给你一个整数 $n$ 和 $k$ 个区间。第 $i$ 个区间为 $[l_i,r_i]$，其中 $1 \leq l_i \leq r_i \leq n$。

我们称一个长度为 $n$ 的正规括号序列$^{\dagger,\ddagger}$ 是超正规的，如果对每个满足 $1 \leq i \leq k$ 的 $i$，子串 $\overline{s_{l_i} s_{l_{i}+1} \ldots s_{r_i}}$ 本身也是一个正规括号序列。

你的任务是计算超正规括号序列的个数。由于该数目可能非常大，你只需输出其对 $998\,244\,353$ 取模的结果。

$^\dagger$ 括号序列是指仅由字符 "(" 和 ")" 组成的字符串。

$^\ddagger$ 若一个括号序列可通过添加字符 "+" 和 "1" 而变成一个合法的数学表达式，则称其为正规的。例如，序列 (())(), (), (()(())) 以及空串是正规的，而 )(、(() 和 (()))( 则不是。

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$, $0 \le k \le 3 \cdot 10^5$) — the length of the hyperregular bracket sequences and the number of intervals respectively.

The following $k$ lines of each test case contains two integers $l_i$ and $r_i$ ($1 \le l \le r \le n$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $3 \cdot 10^5$ and the sum of $k$ across all test cases does not exceed $3 \cdot 10^5$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $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_i \le r_i \le n$）。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$，且所有测试用例中 $k$ 的总和不超过 $3 \cdot 10^5$。

For each test case, output the number of hyperregular bracket sequences modulo $998\,244\,353$.

对于每个测试用例，输出超正则括号序列的数量对 $998\,244\,353$ 取模的结果。

• For the first testcase, the $5$ hyperregular bracket strings of length $6$ are: ((())), (()()), (())(), ()(()) and ()()().

• For the second testcase, there are no regular bracket strings of length $5$, and consequently, there are no hyperregular bracket strings of length $5$.

• For the third testcase, there are no hyperregular bracket strings of length $8$ for which the substring $[1 \ldots 3]$ is a regular bracket string.

• For the fourth testcase, there $4$ hyperregular bracket strings are: ((())(())), ((())()()), ()()((())) and ()()(()())

• 对于第一个测试用例，长度为 $6$ 的 $5$ 个超正则括号串为：((())), (()()), (())(), ()(()) 和 ()()()。

• 对于第二个测试用例，不存在长度为 $5$ 的正则括号串，因此也不存在长度为 $5$ 的超正则括号串。

• 对于第三个测试用例，不存在长度为 $8$ 的超正则括号串，使得其子串 $[1 \ldots 3]$ 是一个正则括号串。

• 对于第四个测试用例，存在 $4$ 个超正则括号串：((())(())), ((())()()), ()()((())) 和 ()()(()())。