You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

静止的数阵再优美也会看腻，所以 $Alice$ 尝试对这个数阵做最简单的变换：交换一列中的两个数字。

当然，经过若干次交换后，$Alice$ 仍然希望这个数阵的两行都是 $1\sim n$ 的排列。

$Alice$ 每天都希望看到不同的优美的数阵，所以请算出通过任意次（可以是 $0$ 次）交换一列中的两个数字，能造出多少个不同的优美的数阵。由于答案可能很大，你只需要输出其对 $10^9 + 7$ 取模后的值。

Format

Input

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

第一行一个整数$n$。

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

Output

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

Samples

样例输入

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

样例输出

4
2

样例解释

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

Limitation

对于 $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 \sum{n} \leq 4 \times 10^5 ，1 \leq p_{i, j} \leq n $ 分别构成 $1 \sim n$ 的排列。