定义一个 二进制字符串中的 块 (由字符组成的字符串 0 和/或 1)作为其相同类型的连续字符子串,不能向左或向右扩展。例如,在字符串中 110001111,共有三个块:
- 11 (从 $$$1$$$-st 字符到 $$$2$$$-nd 字符);
- 000 (从第$$$3$$$个字符到第$$$5$$$个字符);
- 1111 (从第 $$$6$$$ 个字符到第 $$$9$$$ 个字符)。
从第 $$$7$$$ 字符到第 $$$9$$$ 字符的子字符串 111 不是一个块,因为它可以向左扩展。从第 $$$1$$$ 个字符到第 $$$5$$$ 个字符的子字符串 11000 不是一个块,因为它包含不同类型的字符。
我们称一个字符串 美丽 如果我们可以删除 正好一个块 ,以便生成的字符串包含 奇数 块数。例如:
- 字符串 110001111 很漂亮,因为我们可以删除从 $$$3$$$-rd 到第 $$$5$$$ 个字符的块,从而得到字符串 111111,由一个块组成;
- 字符串 1010 很漂亮,因为我们可以删除从 $$$1$$$-st 到 $$$1$$$-st 字符的块,从而得到字符串 010,由三个块组成;
- 字符串 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$$$ 的数量:
- 对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$i$$$,字符串 $$$s[l_i:r_i]$$$ 都很漂亮。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一个整数——满足条件的字符串数量。由于它可能很大,因此输出它对 $$$998244353$$$ 取模。
示例
输入复制
34 31 22 33 44 21 23 4200 113 37
输出复制
24570529459
注意
在该语句的第一个示例中,以下字符串是合适的: 1010, 0101。对于每个字符串,$$$s[1:2]$$$、$$$s[2:3]$$$ 和 $$$s[3:4]$$$ 都很漂亮。