问题描述

小$A$是画画大师。这天他找了一张$n*n$的方格图，初始全是白的，他拿着一只大毛笔从左上角开始，连续地向下向右涂，一直涂到右下角，然后再连续地向上向左涂，一直涂回左上角。涂过的格子都会变成黑色，涂两次和涂一次效果相同。

现在小$B$想要研究小$A$的杰作。由于某种原因，小$B$不知道小$A$画的具体图形，他只知道每行和每列分别有多少个格子被涂黑了。

现在小$B$想知道小$A$的画法总共有多少种不同的可能。两种画法不同当且仅当某一步小$A$的毛笔走的方向不同。即可能有多种画法画出的是同一幅图形，需要算多次。

方案数对$10^9+7$取模。

输入格式

第一行一个整数$T$表示数据组数。$0 \le T \le 30$。对于每组数据：

第一行一个整数$n$。

第二行$n$个非负整数$A_i$，分别表示每一行涂黑的格子数目。

第三行$n$个非负整数$B_i$，分别表示每一列涂黑的格子数目。

输出格式

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

样例一

input

3
2
2 2
2 2
2
1 1
1 1
3
2 2 1
1 2 2

output

2
0
1

数据规模

$20\%$的数据，$n \leq 5$。

$40\%$的数据，$n \leq 1000$。

另有$20\%$的数据，保证不会无解。

$100\%$的数据，$n \leq 100000$。$0 \leq A_i,B_i \leq n$。