蔚（Vi）和艾克（Ekko）正在齐心协力绘制祖安（Zaun）的地图。在祖安城内，一个地下通道网络连接着 $N$ 个地点，标记为 $1$ 到 $N$。该网络形成一个连通系统，其中任意两个地点之间恰好存在一条唯一的路径，且每条通道段连接两个地点。

艾克从野火帮的藏身处（地点 1）出发，蔚从最后一杯（The Last Drop，地点 2）出发，两人各自独立测量了到达网络中每个其他地点所需的通道段的确切数量。给定艾克和蔚的起点出发的这些距离测量值，请确定在满足两组记录距离的情况下，可能存在多少种唯一的通道网络布局。由于答案可能非常大，请输出答案模 $10^9 + 7$ 的结果。蔚或艾克有可能犯了错误，导致根据他们的测量值不存在任何可能的布局。

输入格式

第一行输入一个整数 $N$（$2 \le N \le 10^6$）。

第二行包含 $N$ 个空格分隔的整数 $a_1, a_2, \dots, a_N$（$0 \le a_i \le 10^6$），其中 $a_i$ 是地点 $i$ 到野火帮藏身处的距离。

第三行包含 $N$ 个空格分隔的整数 $b_1, b_2, \dots, b_N$（$0 \le b_i \le 10^6$），其中 $b_i$ 是地点 $i$ 到最后一杯的距离。

野火帮的藏身处位于地点 1，最后一杯位于地点 2。

输出格式

输出一行，包含一个整数，表示唯一的通道网络布局数量模 $10^9 + 7$ 的结果。

样例

输入样例 1

5
0 1 1 1 2
1 0 2 2 3

输出样例 1

2

输入样例 2

3
0 1 1
1 0 1

输出样例 2

0