← 返回题目列表

Codeforces · 2170/E

E. 二进制字符串和块

中文机器翻译题面 查看原题

定义一个 二进制字符串中的 块 (由字符组成的字符串 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$$$ 取模。

示例

输入
复制

3
4 3
1 2
2 3
3 4
4 2
1 2
3 4
200 1
13 37

输出
复制

2
4
570529459

注意

在该语句的第一个示例中,以下字符串是合适的: 1010, 0101。对于每个字符串,$$$s[1:2]$$$、$$$s[2:3]$$$ 和 $$$s[3:4]$$$ 都很漂亮。