数阵交换

题目描述

Alice 有一个 $2 \times n$ 的数字阵列，每行都是 $1 \sim n$ 的排列。可以交换任意列中的两个数字，要求交换后两行仍是 $1 \sim n$ 的排列。求能产生多少个不同的优美数阵，对 $10^9+7$ 取模。

输入格式

第一行 $T$。每组：第一行 $n$；第二、三行各 $n$ 个数表示两行排列。

输出格式

每组输出一行答案。

数据范围

$1 \leq T \leq 10^4$，$2 \leq n \leq 4 \times 10^5$，$\sum n \leq 4 \times 10^5$

样例

样例输入

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

样例输出

4
2