覆盆子 2 - 문제

你的避暑别墅庭院是一个四周被围栏包围的矩形区域。该区域被划分为 $2$ 行 $n$ 列大小为 $1 \times 1$ 的正方形区域。

在其中 $k$ 个正方形区域的中心生长着覆盆子植株，每株植株有四根茎。其他正方形区域是空的。你想把这些植株系到围栏上（作为一个园丁，你自然有你自己的理由这么做）。

要系住一株植株，你可以将其茎沿地面拉成一条直线伸向围栏，并系在对应的围栏段上。你只能沿平行于围栏的方向（上、下、左、右）拉伸茎。这样的茎被称为活跃的（active）。

一个系绳配置（tying configuration）是指一组将植株与围栏连接起来的活跃的茎。每株植株可以被连接多次，也可以完全不连接。

如果满足以下条件之一，我们称一个系绳配置是不稳定的（unstable）：

所有其他配置都是稳定的（stable）。

几年前，你找到了能系住最多植株数量的最优配置。但今天，你问了自己一个不同的问题：稳定配置的总数是多少？由于这个数量可能很大，请将其对 $998\,244\,353$ 取模后输出。

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^9$，$1 \le k \le \min(10^6, 2 \cdot n)$）：表示庭院的大小和覆盆子植株的数量。

接下来的 $k$ 行，每行包含两个整数 $r_i$ 和 $c_i$（$1 \le r_i \le 2$，$1 \le c_i \le n$）：表示含有覆盆子植株的正方形区域的行号和列号。每个测试用例中，每个数对 $(r_i, c_i)$ 最多出现一次。

所有测试用例中 $k$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数：稳定配置的总数。由于这个数量可能很大，请将其对 $998\,244\,353$ 取模后输出。

144
64

我们为样例提供了三幅插图：

第一个测试用例的稳定配置

第一个测试用例的不稳定配置。两根茎相交

第二个测试用例的不稳定配置。来自下方覆盆子植株的茎穿过了另一株覆盆子植株

QOJ.ac