Problem Description

You want to build a wall consisting of $N$ segments, where each segment $i$ can have a height of either $a_i$ or $b_i$. For each possible sequence of wall heights $h$, you want to calculate the total amount of water that can be trapped.

For example, the diagram below shows an example with $N = 10$ and wall heights $4, 2, 1, 8, 6, 2, 7, 1, 2, 3$. The actual water heights are $4, 4, 4, 8, 7, 7, 7, 3, 3, 3$.

Formally, for each possible water height $H$ at position $i$, there must exist a range $l \leq i \leq r$ such that $h_l \geq H$ and $h_r \geq H$. The amount of water trapped at position $i$ is $H - h_i$.

Output the sum of the trapped water amounts for all possible wall configurations, modulo $10^9 + 7$.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $a_i$.

The third line contains $N$ integers $b_i$.

Output Format

Output the sum of the trapped water amounts for all possible wall configurations, modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

4
1 1 1 1
2 2 2 2

Sample Output #1

6

Sample Input #2

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

Sample Output #2

21116

Notes/Hints

For the first sample, the configurations $(2,1,1,2)$, $(1,2,1,2)$, $(2,1,2,1)$, $(2,1,2,2)$, and $(2,2,1,2)$ each trap $1$ unit of water, while $(2,2,2,2)$ traps $2$ units of water.

For all data, $1 \leq N \leq 5 \times 10^5$ and $1 \leq a_i,b_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分