Background

Translated from BalticOI 2024 Day2 T3.

Problem Description

You want to build a wall consisting of $N$ segments. Each segment $i$ can have height $a_i$ or $b_i$. For every possible wall height sequence $h$, you want to compute the total amount of trapped water, and then sum this value over all possible sequences.

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

For a position $i$, the water level $H$ after rain must satisfy that there exist two indices $l, r$ $(l \leq i, r \geq i)$ such that $h_l \geq H$ and $h_r \geq H$, and $H$ is as large as possible. Then the trapped water amount at position $i$ is $H - h_i$.

Output the sum of trapped water over all possible cases, 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 trapped water over all possible wall configurations, modulo $10^9 + 7$.

4
1 1 1 1
2 2 2 2

6

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

21116

Hint

For sample 1, the case $(2,1,1,2)$ has trapped water amount $2$. The cases $(1,2,1,2)$, $(2,1,2,1)$, $(2,1,2,2)$, and $(2,2,1,2)$ each have trapped water amount $1$.

Constraints for all testdata: $1 \leq N \leq 5 \times 10^5$, $1 \leq a_i, b_i \leq 10^9$, and for each $1 \leq i \leq N$, $a_i \neq b_i$.

Translated by ChatGPT 5