CF1534C Little Alawn's Puzzle

当他不在为 IOI 训练时，Little Alawn 喜欢玩各种类型的益智游戏来锻炼大脑。今天，他正在玩一个由 $2 \times n$ 的网格组成的谜题，其中每一行都是 $1,2,3,\ldots,n$ 的一个排列。 Little Alawn 的谜题目标是确保同一列或同一行中没有相同的数字（我们称这种状态为“已解”），为此他可以交换任意一列中的两个数字。然而，在多次解开谜题后，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 个样例的两种可能谜题配置为： - 第一行为 $[1,4,2,3]$，第二行为 $[3,2,1,4]$； - 第一行为 $[3,2,1,4]$，第二行为 $[1,4,2,3]$。 由 ChatGPT 4.1 翻译