你有一个 $$$n \times n$$$ 棋盘,你和计算机轮流分别在棋盘上放置白车和黑车。在放置车时,您必须确保没有两个车互相攻击。如果两只车共享同一行或同一列,则无论颜色如何,它们都会互相攻击。
有效的移动是将车放置在位置 ($$$r$$$, $$$c$$$) 上,这样它就不会攻击任何其他车。
你先开始,当你在你的回合中做出有效的移动,在位置($$$r$$$,$$$c$$$)放置一个白车时,计算机将镜像你并依次在位置($$$c$$$,$$$r$$$)放置一个黑车。如果$$$r = c$$$,那么计算机无法镜像你的移动,并跳过它的回合。
您已经在计算机上玩了 $$$k$$$ 步(计算机也尝试镜像这些步),您必须继续玩游戏,直到没有剩余的有效步。当您在 $$$k$$$ 移动后继续游戏时,可能有多少种不同的最终配置?保证 $$$k$$$ 走法和隐含的计算机走法有效。由于答案可能很大,因此打印它对 $$$10^9+7$$$ 取模。
如果存在一个坐标 ($$$r$$$, $$$c$$$),其中一个配置中有车,但在另一个配置中没有车,或者坐标上车的颜色不同,则认为两个配置不同。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$0 \leq k \leq n$$$) - 分别是棋盘的大小和你已经下过的步数。
测试用例的接下来的 $$$k$$$ 行都包含两个整数 $$$r_i$$$ 和 $$$c_i$$$,表示您进行的第 $$$i$$$ 步。
保证 $$$k$$$ 走法和隐含的计算机走法有效。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,在新行中输出一个整数 - 可能的最终配置总数以 $$$10^9+7$$$ 为模。
示例
输入 #1
3 4 1 1 2 8 1 7 6 1000 4 4 4 952 343 222 333 90 91
输出 #1
3 331 671968183
注意
在第一个测试用例中,我们有一个 $$$4 \times 4$$$ 网格,并且您已经下了 $$$1$$$ 棋步。在你和计算机玩完一个回合后,我们在 ($$$1$$$, $$$2$$$) 处有一个白车,在 ($$$2$$$, $$$1$$$) 处有一个黑车。此状态有三种可能的配置 -
1. 您将白车放置在 ($$$3$$$, $$$4$$$) 处,计算机将黑车放置在 ($$$4$$$, $$$3$$$) 作为响应。
2. 您将白车放置在 ($$$4$$$, $$$3$$$) 处,计算机将黑车放置在 ($$$3$$$, $$$4$$$) 作为响应。
3. 您将白车放置在 ($$$3$$$, $$$3$$$) 处,然后放置在 ($$$4$$$, $$$4$$$) 处,或者反之亦然。它们都产生相同的配置。