14 世纪，特拉凯岛城堡（Trakai Island Castle）即将开始动工。首席建筑师清单上的第一项任务是规划主城堡墙的建造。

建造一堵能保护城堡免受任何可能攻击的墙是非常棘手的。为了确保城堡驻军的安全，首席建筑师已经缩小了设计空间。

由于来自湖中心的攻击不如来自附近岸边的攻击那样频繁，墙不需要形成一个闭环。相反，它将呈直线形状，由 $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, 3$。

形式上，对于每个 $i = 1, 2, \dots, N$，位置 $i$ 的水位至少为 $h$ 当且仅当存在整数 $l$ 和 $r$，使得 $l \le i$ 且 $i \le r$，并且位置 $l$ 和 $r$ 的段高度至少为 $h$。特别地，位置 $1$ 和 $N$ 的水位总是等于相应段的高度，且任何位置的水位总是至少与相应段的高度一样大。位置 $i$ 积聚的水量等于水位与段高度之差。积聚的总水量就是位置 $1, 2, \dots, N$ 处积聚水量的总和。

任务

你的任务是计算所有 $2^N$ 种可能的墙中，积聚水量的总和。你应该输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$。 第三行包含 $N$ 个整数 $b_1, b_2, \dots, b_N$。

输出格式

你的程序应输出一个整数，即所有 $2^N$ 种可能的墙中积聚水量的总和，对 $10^9 + 7$ 取模。

样例

样例输入 1

4
1 1 1 1
2 2 2 2

样例输出 1

6

说明 1

存在一种可能的墙，其中积聚了两个单位的水： * $2, 1, 1, 2$

以及四种可能的墙，其中积聚了一个单位的水： $1, 2, 1, 2$ $2, 1, 2, 1$ $2, 1, 2, 2$ $2, 2, 1, 2$

样例输入 2

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

样例输出 2

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$）。

子任务