CF2170E.Binary Strings and Blocks

Define a block in a binary string (a string consisting of characters 0 and/or 1) as its continuous substring of characters of the same type that cannot be extended either to the left or to the right. For example, in the string 110001111, there are three blocks:

• 11 (from the $1$-st character to the $2$-nd character);
• 000 (from the $3$-rd character to the $5$-th character);
• 1111 (from the $6$-th character to the $9$-th character).

The substring from the $7$-th character to the $9$-th character 111 is not a block because it can be extended to the left. The substring from the $1$-st character to the $5$-th character 11000 is not a block because it contains characters of different types.

We call a string beautiful if we can remove exactly one block from it so that the resulting string consists of an odd number of blocks. For example:

• the string 110001111 is beautiful because we can remove the block from the $3$-rd to the $5$-th character, resulting in the string 111111, which consists of one block;
• the string 1010 is beautiful because we can remove the block from the $1$-st to the $1$-st character, resulting in the string 010, which consists of three blocks;
• the string 0000 is not beautiful because the only way to remove a block from it will result in an empty string, which consists of $0$ blocks.

You are given an integer $n$ and $m$ constraints, the $i$-th of which is described by a pair of integers $l_i, r_i$. We denote the substring of the string $s$ from character $l$ to character $r$ inclusive as $s[l:r]$, that is, $s[l:r] = s_l s_{l+1} \dots s_r$. Your task is to count the number of binary strings $s$ of length $n$ meeting the following condition:

• for each $i$ from $1$ to $m$, the string $s[l_i:r_i]$ is beautiful.

在二进制字符串（即仅由字符 0 和/或 1 组成的字符串）中，我们定义一个块（block）为：该字符串中一个极大连续子串，其中所有字符均相同，且无法向左或向右延伸。例如，在字符串 110001111 中，存在三个块：

• 11（从第 $1$ 个字符到第 $2$ 个字符）；
• 000（从第 $3$ 个字符到第 $5$ 个字符）；
• 1111（从第 $6$ 个字符到第 $9$ 个字符）。

子串 111（从第 $7$ 个字符到第 $9$ 个字符）不是一个块，因为它可以向左延伸；子串 11000（从第 $1$ 个字符到第 $5$ 个字符）也不是一个块，因为它包含不同类型（0 和 1）的字符。

我们称一个字符串是优美的（beautiful），如果从中恰好移除一个块后，所得字符串所含的块数为奇数。例如：

• 字符串 110001111 是优美的，因为我们可以移除第 $3$ 至第 $5$ 个字符构成的块（即 000），得到字符串 111111，它仅含 1 个块；
• 字符串 1010 是优美的，因为我们可以移除第 $1$ 至第 $1$ 个字符构成的块（即 1），得到字符串 010，它含有 3 个块；
• 字符串 0000 不是优美的，因为从中移除唯一可能的一个块（即整个字符串 0000）后，结果为空字符串，它含有 $0$ 个块（偶数）。

给定一个整数 $n$ 和 $m$ 个约束条件，其中第 $i$ 个约束由一对整数 $l_i, r_i$ 描述。我们记字符串 $s$ 从第 $l$ 个字符到第 $r$ 个字符（含端点）的子串为 $s[l:r]$，即 $s[l:r] = s_l s_{l+1} \dots s_r$。你的任务是：统计满足以下条件的长度为 $n$ 的二进制字符串 $s$ 的个数：

• 对每个 $i$（$1 \le i \le m$），子串 $s[l_i:r_i]$ 是优美的。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test case.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$; $1 \le m \le 3 \cdot 10^5$) — the required length of the string and the number of constraints, respectively.

Next, there are $m$ lines, the $i$-th of which contains two integers $l_i, r_i$ ($1 \le l_i \lt r_i \le n$) — the description of the $i$-th constraint.

Additional constraints on the input:

• The sum of $n$ across all test cases does not exceed $3 \cdot 10^5$;
• The sum of $m$ across all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$；$1 \le m \le 3 \cdot 10^5$）—— 分别表示所要求的字符串长度和约束条件的数量。

接下来有 $m$ 行，其中第 $i$ 行包含两个整数 $l_i, r_i$（$1 \le l_i \lt r_i \le n$）—— 描述第 $i$ 个约束条件。

输入的附加约束：

• 所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$；
• 所有测试用例中 $m$ 的总和不超过 $3 \cdot 10^5$。

For each test case, print one integer — the number of strings that satisfy the condition. Since it may be huge, output it modulo $998244353$.

对于每个测试用例，输出一个整数——满足条件的字符串数量。由于该数值可能很大，请对 $998244353$ 取模后输出。

In the first example from the statement, the following strings are suitable: 1010, 0101. For each of these strings, both $s[1:2]$, $s[2:3]$, and $s[3:4]$ are beautiful.

在题目陈述的第一个例子中，以下字符串是符合条件的：1010、0101。对于每个这样的字符串，$s[1:2]$、$s[2:3]$ 和 $s[3:4]$ 均为优美的。