CF2056E Nested Segments

如果 $1\le l\le r\le n$ 且 $A$ 中任何一对不同的线段 $[l_i, r_i], [l_j, r_j]$ 都恰好满足以下条件之一，那么由具有整数端点的成对不同线段 $[l, r]$ 组成的集合 $A$ 是好的： - $r_i < l_j$ 或 $r_j < l_i$ （线段不相交） - $l_i \le l_j \le r_j \le r_i$ 或 $l_j \le l_i \le r_i \le r_j$ （一条线段完全包含在另一条线段中） 给你一个由 $m$ 对不同的线段 $[l_i, r_i]$ 组成的好的集合 $S$。您希望在确保集合 $S$ 是好的的前提下，尽可能多地向集合 $S$ 添加线段。 由于这项任务过于简单，因此您需要确定有多少种不同的方法可以在确保集合 $S$ 是好的的情况下，向 $S$ 添加最大数量的额外线段。如果在其中一种方法中增加了一条线段，而在另一种方法中没有增加，那么这两种方法就被认为是不同的。 形式化的，我们需要找出由不同的线段组成的好的的集合 $T$ 的个数，使得 $S$ 是 $T$ 的子集，且 $T$ 的大小最大。由于结果可能很大，请计算答案对 $998\,244\,353$ 取模后的结果。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（ $1 \le t \le 10^4$ ）。测试用例说明如下。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \times 10^5$）—线段的最大右端点和 $S$ 的大小。 接下来 $m$ 行的 $i$\-th 包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）—即集合 $S$ 中的线段边界。 保证给定的集合 $S$ 是好的，并且集合 $S$ 中的线段是成对不同的。 保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示在确保集合 $S$ 是好的的情况下，在集合 $S$ 中添加最大数量的额外线段的不同方式的数量，模数为 $998\,244\,353$ 。

在第一个例子中，唯一可能的线段是 $[1, 1]$ ，因此 $T = \{[1, 1]\}$ 的大小最大，也是唯一的解。 在第二个示例中，无法向集合 $S$ 添加任何额外的线段。因此，向 $S$ 添加线段的唯一方法就是不添加任何线段。 在第三个例子中，在确保集合 $S$ 仍然良好的情况下，可以向 $S$ 添加 $7$ 条额外的线段。我们可以证明，在 $S$ 中添加超过 $7$ 条线段是不可能的。恰好有 $2$ 种不同的方法可以将这些 $7$ 条线段添加到 $S$ 中，它们各自的集合 $T$ 如下所示： - $\{[1, 1], [1, 3], [1, 4], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [5, 5]\}$ - $\{[1, 1], [1, 3], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [4, 5], [5, 5]\}$ . 在第四个例子中，正好有 $5$ 种不同的方法可以将最多 $6$ 条额外的线段添加到 $S$ 中，它们各自的集合 $T$ 如下所示： - $\{[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [3, 3], [4, 4]\}$ - $\{[1, 1], [1, 2], [1, 4], [2, 2], [3, 3], [3, 4], [4, 4]\}$ - $\{[1, 1], [1, 3], [1, 4], [2, 2], [2, 3], [3, 3], [4, 4]\}$ - $\{[1, 1], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [4, 4]\}$ - $\{[1, 1], [1, 4], [2, 2], [2, 4], [3, 3], [3, 4], [4, 4]\}$