题目描述

Alice 有一个 $2 \times n$ 的数字阵列，也就是两行，每行 $n$ 个数字。因为排列的性质是优美的，所以 Alice 让每行初始化是 $1 \sim n$ 的排列。

静止的数组再优美也会看腻，所以 Alice 尝试对这个数组做最简单的变换：交换一列中的两个数字。当然，经过若干次交换，Alice 仍然希望这个数组的两行都是 $1 \sim n$ 的排列。

Alice 每天都希望看到不同的优美数组，所以请求计算通过任意次（可以是 0 次）交换一列中的两个数字，能造出多少个不同的优美数组。称两个优美的数组不同，当且仅当存在某一列在其中一个数组中执行了交换，而另一个数组没有。

由于答案可能很大，你只需要输出其对 $10^9 + 7$ 取模后的值。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行一个整数 $n$。

第二、三行每行 $n$ 个数字 $p_{i,j}$，分别表示数组两行的元素。

输出格式

对于每组数据，输出一行一个整数表示答案对 $10^9 + 7$ 取模后的值。

2
4
1 2 3 4
4 3 2 1
5
1 3 5 2 4
2 4 1 3 5

4
2

提示

样例解释：对于第二组数据，只有不交换和同时交换每一列中的两个数字才能使得最终得到的数阵是优美的。

数据范围

• 对于 30% 的数据，$1 \leq T \leq 10, \ 2 \leq n \leq 18$。
• 对于 60% 的数据，$1 \leq T \leq 10, \ 2 \leq n \leq 1000$。
• 对于 100% 的数据，$1 \leq T \leq 10^4, \ 2 \leq n \leq 4 \times 10^5, \ \sum n \leq 4 \times 10^5$，$1 \leq p_{i,j} \leq n$，$p_1, p_2$ 分别构成 $1 \sim n$ 的排列。