继天才的“品红方块”和非传统的“紫红色圆圈”之后，世界著名艺术家 Theodore Cadman Spencer 正在创作他的下一部杰作。这一次，这位大师真正超越了自己，因为这件艺术品无法用单一的几何形状来描述，这显然是 Theodore 在通往圆满的旅程中迈出的一大步。

这位大师决定使用一块巨大的画布，形状为一个 $n \times n$ 的正方形，被完美地划分为 $1 \times 1$ 的小方格。画布最初是全白的，艺术家将用画笔将其中一些方格涂成栗色。

Theodore 的构思是：将画笔放在画布的左上角（即第一行第一列），然后轻轻地将其滑向右下角，移动过程中始终只能向右或向下移动一格。画笔经过的所有方格都会立即变成栗色。但令人难以置信的是，这并不是这位天才画家计划的终点！一旦他到达右下角，他就会折返，通过向左或向上移动，最终回到他开始的方格。他可以自由选择路径，而那些被涂过两次的方格在外观上不会有任何改变。

你是 Spencer 作品的忠实粉丝，也是一名新手黑客——你无法抗拒诱惑，潜入了艺术家的电脑，试图下载他杰作的草图。然而，文件巨大的体积使这变得不可能，所以你迅速地以以下方式对其进行了压缩：对于 $n$ 行中的每一行，你计算了该行中栗色方格的数量；然后，你对 $n$ 列中的每一列也做了同样的操作。最后，你将这些数值保存到了本地服务器上，并在被发现之前逃之夭夭。

现在，你感到不满足——你想知道导致这件杰作诞生的确切过程，而你对你得到的压缩形式毫不在意。但这些信息到底能告诉你多少呢？请计算出与你所掌握的信息相符的画笔路径数量。如果艺术家在某一时刻选择了不同的方向，则认为两条路径不同。注意，两条不同的路径可能会导致相同的绘画结果，但你非常看重创作过程，因此你将它们视为不同的路径。

由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 30$)。接下来是各测试用例的描述。

每个测试用例的第一行包含画布的大小 $n$ ($1 \le n \le 100\,000$)。每个测试用例的第二行包含 $n$ 个整数 $r_i$ ($0 \le r_i \le n$)，表示绘画中每一行的栗色方格数量。下一行以相同的格式描述了各列的栗色方格数量。

输出格式

对于每个测试用例，输出一个整数：与给定信息相符的路径数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

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

样例输出 1

2
0
1