Description

The COCI problem setters must choose the tasks that will appear in the next round from a pool of tasks.

The difficulty of a task is described by an integer from $1$ to $n$, but for some tasks it is not easy to determine their difficulty accurately. The COCI problem setters believe that such tasks can be treated as having one of two consecutive difficulties. For example, some tasks can be treated as having difficulty $3$ or $4$.

The next COCI round will contain $N$ tasks. For each difficulty, there will be exactly one task. Of course, no task will appear twice.

Find the number of different ways the setters can choose the tasks for the next round. We consider two ways different only if the same task is assigned to different difficulties.

Since the expected result can be very large, output the number of ways $\% 10^9+7$.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_i$, where the $i$-th number represents the number of tasks whose difficulty is exactly $i$.

The third line contains $N-1$ integers $B_i$, where the $i$-th number represents the number of tasks whose difficulty is $i$ or $i+1$.

Output Format

Output one line with an integer, representing the number of ways $\% 10^9+7$.

3
3 0 1
0 1 

3

4
1 5 3 0
0 2 1 

33

Hint

[Sample Explanation #1]

There are $3$ ways in total: treat the tasks with difficulty $2$ or $3$ as difficulty $2$. Since there are $3$ tasks with difficulty $1$, there are $3$ ways in total.

[Constraints]

For $100\%$ of the testdata, $2 \le N \le 10^5$, $0 \le A_i, B_i \le 10^9$.

[Notes]

The score of this problem follows the original COCI setting, with a full score of $100$.

This problem is translated from COCI2010-2011 CONTEST #5 T4 HONI.

Translated by ChatGPT 5