P10764 [BalticOI 2024] Wall

Translated from [BalticOI 2024 Day2 T3](https://boi2024.lmio.lt/tasks/d2-wall-statement.pdf).

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$.

The first line contains an integer $N$. The second line contains $N$ integers $a_i$. The third line contains $N$ integers $b_i$.

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

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$. | Subtask ID | Special Property | Points | | :-----------: | :----------- | :-----------: | | $1$ | $N \leq 20$ | $8$ | | $2$ | $N \leq 100$ and $a_i, b_i \leq 1000$ | $17$ | | $3$ | $N \leq 10000$ and $a_i, b_i \leq 1000$ | $19$ | | $4$ | $N \leq 10000$ | $14$ | | $5$ | $a_i, b_i \leq 2$ | $12$ | | $6$ | No special property | $30$ | 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