← 返回题目列表

Codeforces · 1957/C

C. 车如何移动?

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

你有一个 $$$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$$$) 处,或者反之亦然。它们都产生相同的配置。