Description

As everyone knows, Balázs has the most beautiful fence in the whole town. The fence consists of $N$ sections. Each section is a rectangle, and any two adjacent sections are tightly connected. The $i$-th rectangle has height $h_i$ and width $w_i$. We need to find “fancy rectangles” that satisfy the following conditions:

• Each side of the rectangle is horizontal or vertical, and the length of each side is an integer.
• The distance from the rectangle to the ground is an integer.
• The distance from the rectangle to the left side of the first section of the fence is an integer.
• The rectangle is completely contained within the fence.

Now you need to compute the total number of fancy rectangles. Since this number may be very large, output it modulo $10^9+7$.

Input Format

The first line contains an integer $N$, meaning the fence consists of $N$ sections.

The second line contains $N$ integers. The $i$-th integer is the height $h_i$ of the $i$-th rectangle.

The third line contains $N$ integers. The $i$-th integer is the width $w_i$ of the $i$-th rectangle.

Output Format

Output the number of fancy rectangles modulo $10^9+7$.

2
1 2
1 2

12

Hint

Sample Explanation 1

The shape of the fence is as shown below:

There are $5$ rectangles of the following shape:

There are $3$ rectangles of the following shape:

There is $1$ rectangle of the following shape:

There are $2$ rectangles of the following shape:

There is $1$ rectangle of the following shape:

Sample 2

See the additional file.

Subtasks

All test points satisfy: $1 \leq N \leq 10^5$, $1 \leq h_i,w_i \leq 10^9$.

The constraints for each subtask are as follows:

Translated by ChatGPT 5