CF1534C.Little Alawn's Puzzle

When he's not training for IOI, Little Alawn enjoys playing with puzzles of various types to stimulate his brain. Today, he's playing with a puzzle that consists of a $2 \times n$ grid where each row is a permutation of the numbers $1,2,3,\ldots,n$.

The goal of Little Alawn's puzzle is to make sure no numbers on the same column or row are the same (we'll call this state of the puzzle as solved), and to achieve this he is able to swap the numbers in any column. However, after solving the puzzle many times, Little Alawn got bored and began wondering about the number of possible solved configurations of the puzzle he could achieve from an initial solved configuration only by swapping numbers in a column.

Unfortunately, Little Alawn got stuck while trying to solve this harder problem, so he was wondering if you could help him with it. Find the answer modulo $10^9+7$.

当小阿尔万（Little Alawn）不为国际信息学奥林匹克竞赛（IOI）训练时，他喜欢玩各种类型的益智游戏来锻炼大脑。今天，他正在玩一个由 $2 \times n$ 网格构成的谜题，其中每一行都是数字 $1, 2, 3, \ldots, n$ 的一个排列。

小阿尔万这个谜题的目标是：确保同一列或同一行中不出现相同的数字（我们将满足该条件的状态称为“已解状态”）；而为了达成这一目标，他可以任意交换任意一列中的两个数字。然而，在多次解出该谜题后，小阿尔万感到厌倦，开始思考这样一个更难的问题：从一个初始的已解状态出发，仅通过交换各列内的数字，总共能到达多少种不同的已解状态？

不幸的是，小阿尔万在尝试解决这个更难的问题时卡住了，因此他想知道你能否帮他解答。请输出答案对 $10^9+7$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 4 \cdot 10^5$).

The next two lines of each test case describe the initial state of the puzzle grid. Each line will be a permutation of the numbers $1,2,3,\ldots,n$ and the numbers in each column and row will be pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case output a single integer, the number of possible solved configurations of the puzzle Little Alawn can achieve from an initial solved configuration only by swapping numbers in a column. As the answer can be very large, please output it modulo $10^9+7$.

The answer for each test case should be on a separate line.

对于每个测试用例，输出一个整数，表示小 Alawn 仅通过交换某一列中的数字，从初始已解状态所能达到的不同已解状态的数量。由于答案可能非常大，请将结果对 $10^9+7$ 取模后输出。

每个测试用例的答案应单独占一行。

The two possible puzzle configurations for example $1$ are:

• $[1,4,2,3]$ in the first row and $[3,2,1,4]$ in the second;
• $[3,2,1,4]$ in the first row and $[1,4,2,3]$ in the second.

示例 $1$ 的两种可能谜题配置为：

• 第一行是 $[1,4,2,3]$，第二行是 $[3,2,1,4]$；
• 第一行是 $[3,2,1,4]$，第二行是 $[1,4,2,3]$。