背景

翻译自 BalticOI 2024 Day2 T3。

题目描述

你想要修建一个围墙，它是由 $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$ 取模的值。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $a_i$。

第三行 $N$ 个整数 $b_i$。

输出格式

输出可能的围墙积水量之和对 $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

提示

对于样例一，$(2,1,1,2)$ 的情况存在 $2$ 的积水量，$(1,2,1,2)$，$(2,1,2,1)$，$(2,1,2,2)$，$(2,2,1,2)$ 分别存在 $1$ 的积水量。

对于所有数据 $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$。