31973번 - Flooding Wall 서브태스크다국어

문제

It's the 14th century and construction of the Trakai Island Castle is to begin soon. The first task on the chief architect's list is to plan the construction of the main castle wall.

Building a wall that can protect the castle from any possible attack is quite tricky. To ensure the safety of the castle garrison, the chief architect has already narrowed the design space somewhat.

Since attacks from the middle of the lake aren't as likely as attacks from the nearby shore, the wall does not need to form a closed loop. Instead, it will be in the shape of a straight line, and consist of $N$ segments arranged from one end to the other and numbered 1ドル$ to $N$. What still remains is picking the height of each segment.

The chief architect has already picked two possible heights for each segment. He decided that the height of the $i$-th segment will be either $a_i$ or $b_i$. Thus, 2ドル^N$ possibilities remain.

Having the castle on a small island in a lake has its difficulties. During stormy weather, the castle can get flooded. In such cases, water collects above wall segments if there are higher segments to each side of them, preventing the water from draining.

For a particular choice of the segments’ heights, we are interested in the amount of water that will collect on the wall after a heavy storm. This is illustrated in the following figure, where the segments’ heights from left to right are 4ドル,ドル 2ドル,ドル 1ドル,ドル 8ドル,ドル 6ドル,ドル 2ドル,ドル 7ドル,ドル 1ドル,ドル 2ドル,ドル 3ドル$ and the level of water at each position is 4ドル,ドル 4ドル,ドル 4ドル,ドル 8ドル,ドル 7ドル,ドル 7ドル,ドル 7ドル,ドル 3ドル,ドル 3ドル,ドル 3ドル$.

Formally, for every $i = 1, 2, \dots , N,ドル the level of water at position $i$ is at least $h$ if and only if there exist integers $l$ and $r$ such that $l ≤ i$ and $i ≤ r$ and the segment heights at positions $l$ and $r$ are at least $h$. In particular, the level of water at positions 1ドル$ and $N$ is always equal to the heights of the corresponding segments, and the level of water at any position is always at least as large as the height of the corresponding segment. The amount of water that collects at position $i$ is equal to the difference between the level of water and the height of the segment. The total amount of water collected is just the sum of collected water at positions 1,ドル 2, \dots , N$.

Your task is to compute the sum, over all 2ドル^N$ possible walls, of the total amount of collected water. You should output the answer modulo 10ドル^9 + 7$.

입력

The first line of the input contains one integer number $N$.

The second line of the input contains $N$ integers $a_1 , a_2 , \dots , a_N$.

The third line of the input contains $N$ integers $b_1 , b_2 , \dots , b_N$.

출력

Your program should output a single integer, the sum of the total amount of water collected over all 2ドル^N$ possible walls modulo 10ドル^9 + 7$.

제한

• 1ドル ≤ N ≤ 5 \cdot 10^5$.
• 1ドル ≤ a_i , b_i ≤ 10^9$ and $a_i \ne b_i$ (for all 1ドル ≤ i ≤ N$).

서브태스크

힌트