题目描述

题目译自 BalticOI 2024 Day2「Flooding Wall」

现在是 14 世纪，特拉凯岛城堡的建设即将开始。首席建筑师的首要任务是规划城堡主墙的建造。

建造一道能够保护城堡不受任何可能攻击的城墙是一件相当棘手的事情。为了确保城堡守军的安全，总建筑师已经在一定程度上缩小了设计空间。

由于从湖中央发动进攻的可能性不如从附近岸边发动进攻的可能性大，因此城墙不需要形成一个封闭的环形。相反，它的形状是一条直线，城墙由 $N$ 段这样的直线组成，从一端排列到另一端，编号为 $1$ 到 $N$。剩下的就是选择每段的高度了。

总建筑师已经为每段选择了两种可能的高度。他决定第 $i$ 段的高度为 $a_i$ 或 $b_i$。因此，城墙还剩下 $2^N$ 种可能性。

将城堡建在湖中的一个小岛上也有困难。在暴风雨天气，城堡可能会被淹。在这种情况下，如果某段墙的两侧有较高的墙段，水就会聚集在这段墙的上方，阻止水排出。

对于特定的墙高度选择，我们关心的是暴风雨过后墙面上的积水量。如下图所示，墙从左到右的高度分别为 $4,2,1,8,6,2,7,1,2,3$，每个位置的水位分别为 $4,4,4,8,7,7,7,3,3$。

形式上，对于每个 $i = 1,2,\ldots, N$，位置 $i$ 处的水位至少为 $h$，当且仅当存在整数 $l$ 和 $r$，使得 $l\le i$，$i\le r$ 且位置 $l$ 和 $r$ 处的墙高度至少为 $h$。特别地，位置 $1$ 和 $N$ 的水位总是等于相应位置墙的高度，而任何位置的水位总是至少等于相应位置墙的高度。第 $i$ 个位置的集水量等于水位与墙高度之差。收集的总水量是位置 $1,2,\ldots, N$ 的集水量之和。

你的任务是计算所有 $2^N$ 种可能的墙壁的总集水量之和。输出答案对 $10^9 + 7$ 取模的答案。

输入格式

第一行一个整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

第三行包含 $N$ 个整数 $b_1,b_2,\ldots,b_N$。

输出格式

输出一个整数，表示所有 $2^N$ 种可能的墙壁的总集水量之和模 $10^9+7$ 后的值。

4
1 1 1 1
2 2 2 2

6

有一种可能总集水量为 $2$：

• $2\ 1\ 1\ 2$

有四种可能总集水量为 $1$：

• $1\ 2\ 1\ 2$
• $2\ 1\ 2\ 1$
• $2\ 1\ 2\ 2$
• $2\ 2\ 1\ 2$

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

21116

数据范围与提示

对于所有数据，满足：

• $1\le N\le 5\cdot 10^5$
• $1\le a_i,b_i\le 10^9$ 且 $a_i\neq b_i$（对于所有 $1\le i\le N$）

详细子任务附加限制及分值如下表。