← 返回题目列表

Codeforces · 1534/C

C. 小阿劳恩的拼图

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

当他不进行 IOI 训练时,Little Alawn 喜欢玩各种类型的谜题来刺激他的大脑。今天,他正在玩一个由 $$$2 \times n$$$ 网格组成的谜题,其中每一行都是数字 $$$1,2,3,\ldots,n$$$ 的排列。

Little Alawn 谜题的目标是确保同一列或同一行上的数字没有相同(我们将谜题的这种状态称为已解决),并且为了实现这一目标,他能够交换任何列中的数字。然而,在多次解决这个谜题后,小阿劳恩感到无聊,并开始想知道他仅通过交换一列中的数字就可以从初始解决的配置中获得该谜题的可能解决配置的数量。

不幸的是,Little Alawn 在尝试解决这个更难的问题时遇到了困难,所以他想知道你是否可以帮助他解决这个问题。以 $$$10^9+7$$$ 为模求出答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$)。

每个测试用例的接下来两行描述了拼图网格的初始状态。每行都是数字 $$$1,2,3,\ldots,n$$$ 的排列,并且每列和行中的数字将成对不同。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。

输出

对于输出单个整数的每个测试用例,Little Alawn 谜题的可能解决配置数量仅通过交换列中的数字即可从初始解决配置实现。由于答案可能非常大,请输出它对$$$10^9+7$$$取模。

每个测试用例的答案应该位于单独的行上。

示例

输入 #1

2
4
1 4 2 3
3 2 1 4
8
2 6 5 1 4 3 7 8
3 8 7 5 1 2 4 6

输出 #1

2
8

注意

例如 $$$1$$$ 的两种可能的拼图配置是:

- 第一行$$$[1,4,2,3]$$$,第二行$$$[3,2,1,4]$$$;
- 第一行是 $$$[3,2,1,4]$$$,第二行是 $$$[1,4,2,3]$$$。