Problem I
Mapping the Undercity

Vi and Ekko are working together to try to make a map of Zaun. Within the city of Zaun, an underground network of tunnels connects $N$ locations, labeled $1$ through $N$. This network forms a connected system where exactly one unique path exists between any two locations, and each tunnel segment connects two locations. Ekko, starting from the Firelights’ hideout (location $1$), and Vi, starting from the The Last Drop (location $2$), have each independently measured the exact number of tunnel segments required to reach every other location in the network. Given these distance measurements from both Ekko’s and Vi’s starting points, determine how many unique possible layouts of the tunnel network could exist while still satisfying both sets of recorded distances. Since the answer may be very large, find the answer modulo $10^9+7$. It is possible that Vi or Ekko made a mistake so that no possible layout could exist according to their measurements.

Input

The first line of input is an integer $N \: (2 \leq N \leq 10^6)$. The second line contains $N$ space-separated integers, $a_1, a_2 \ldots , a_N \: (0 \leq a_i \leq 10^6)$, where $a_i$ is the distance from location $i$ to the Firelights’ hideout. The third line contains $N$ space-separated integers, $b_1, b_2 \ldots , b_N \: (0 \leq b_i \leq 10^6)$, where $b_i$ is the distance from location $i$ to The Last Drop. The Firelights’ hideout is at location $1$, and The Last Drop is at location $2$.

Output

Output one line containing a single integer, the number of unique tunnel network layouts, modulo $10^9+7$.

5
0 1 1 1 2
1 0 2 2 3

2

3
0 1 1
1 0 1

0