Problem Description

The King of Mizugoro Kingdom, Kagamizu, loves to knock down the tall ones. He often lines up his servants in a row and enjoys shrinking the height of the protruding ones with his hydroponic pump.

As a close aide to the King, you noticed that he doesn't just choose the tallest person to be the target of his hydroponic pump.

According to the King, "In everything, moderation is key. No one who is not at the edge should have a height that is not the average of the heights of their neighbors."

Thus, after a round of using his hydroponic pump, the King is delighted to see a row of servants where everyone's height is equal to the average of the heights of their neighbors.

Seeing this every day, you wondered how many such arrangements of heights could satisfy the King. Given the constraints on each person's height, you decided to count them.

By the way, in Mizugoro Kingdom, people's heights are always integers, and strangely, some people have heights of $ 0 $ or even negative heights.

Input Format

$ N $ $ A_1 $ … $ A_N $ $ B_1 $ … $ B_N $

Output Format

Output the solution to the problem in one line.

Sample Input and Output

Sample Input #1

3
0 0 0
2 2 2

Sample Output #1

5

Sample Input #2

8
-9 -8 -7 -6 -8 -20 -9 -1
6 8 10 16 42 18 14 20

Sample Output #2

42

Sample Input #3

3
-1000000000 -1000000000 -1000000000
1000000000 1000000000 1000000000

Sample Output #3

85

Notes/Hints

Task

Given two integer sequences $ A $ and $ B $ of $ N $ elements each, how many integer sequences $ X $ of $ N $ elements satisfy the following conditions? Output the answer modulo $ 1,000,000,007 $ ($=\ 10^9\ +\ 7$).

• For $i\ =\ 1,\ ...,\ N$, $A_i\ ≦\ X_i\ ≦\ B_i$.
• For $i\ =\ 2,\ ...,\ N\ -\ 1$, $X_i\ =\ \frac{X_{i-1}\ +\ X_{i+1}}{2}$.

Constraints

All input data satisfies the following constraints:

• $3\ ≦\ N\ ≦\ 10^5$.
• $-10^9\ ≦\ A_i\ ≦\ B_i\ ≦\ 10^9$.

Additionally, for the input data worth 2 points, the following constraints are added:

• $N\ ≦\ 100$.
• $-100\ ≦\ A_i\ ≦\ B_i\ ≦\ 100$.

Sample Explanation 1

The sequences $ X $ that satisfy the conditions are:
- $X_1\ =\ 0,\ X_2\ =\ 0,\ X_3\ =\ 0$
- $X_1\ =\ 0,\ X_2\ =\ 1,\ X_3\ =\ 2$
- $X_1\ =\ 1,\ X_2\ =\ 1,\ X_3\ =\ 1$
- $X_1\ =\ 2,\ X_2\ =\ 1,\ X_3\ =\ 0$
- $X_1\ =\ 2,\ X_2\ =\ 2,\ X_3\ =\ 2$

There are 5 such sequences.

Sample Explanation 3

There are $ 2,000,000,002,000,000,001 $ sequences that satisfy the conditions. Note that you should output the number of sequences modulo $ 1,000,000,007 $.

见题面 Input 部分

见题面 Output 部分