[BalticOI 2024] Wall

你想要修建一个围墙，它是由 $N$ 个墙组成的，每个墙 $i$ 可能的高度是 $a_i$ 或 $b_i$，对于每个可能的围墙序列 $h$，你想要求出它的积水量之和。 例如下图展示了一个 $N = 10$，围墙高度分别为 $4, 2, 1, 8, 6, 2, 7, 1, 2, 3$ 的例子，它的实际积水高度是 $4, 4, 4, 8, 7, 7, 7, 3, 3, 3$。  对于某个 $i$ 雨后应有的水位 $H$，需要满足存在两个数 $l,r\ (l \leq i,r\geq i)$，有 $h_l \geq H,h_r \geq H$，且 $H$ 最大，此时 $i$ 的积水量为 $H-h_i$。 输出所有可能情况的积水量之和对 $10^9 +7$ 取模的值。 ## Input 第一行一个整数 $N$。 第二行 $N$ 个整数 $a_i$。 第三行 $N$ 个整数 $b_i$。 ## Output 输出可能的围墙积水量之和对 $10^9 +7$ 取模的值。 [samples] ## Background 翻译自 [BalticOI 2024 Day2 T3](https://boi2024.lmio.lt/tasks/d2-wall-statement.pdf)。 ## Note 对于样例一，$(2,1,1,2)$ 的情况存在 $2$ 的积水量，$(1,2,1,2)$，$(2,1,2,1)$，$(2,1,2,2)$，$(2,2,1,2)$ 分别存在 $1$ 的积水量。 | 子任务编号 | 特殊性质 | 分值 | | :-----------: | :----------- | :-----------: | | $1$ | $N \leq 20$ | $8$ | | $2$ | $N \leq 100$ 且 $a_i,b_i \leq 1000$ | $17$ | | $3$ | $N \leq 10000$ 且 $a_i,b_i \leq 1000$ | $19$ | | $4$ | $N \leq 10000$ | $14$ | | $5$ | $a_i,b_i \leq 2$ | $12$ | | $6$ | 无特殊性质 | $30$ | 对于所有数据 $1 \leq N \leq5 \times10^5$，$1 \leq a_i,b_i \leq 10^9$ 且对于 每个 $1 \leq i \leq n$，有 $a_i \neq b_i$。