홍수 성벽

14세기, 트라카이 섬 성의 건설이 곧 시작된다. 수석 건축가의 목록에서 첫 번째 과제는 성의 주벽 건설을 계획하는 것이다.

어떤 공격이든 막아낼 수 있는 벽을 세우기는 꽤 까다롭다. 성의 수비대를 안전하게 지키기 위해 수석 건축가는 설계 범위를 이미 어느 정도 좁혀 두었다.

호수 한가운데에서 오는 공격은 근처 해안에서 오는 공격보다 가능성이 낮다. 그래서 벽은 닫힌 고리일 필요가 없다. 대신 한쪽 끝에서 다른 쪽 끝까지 일직선으로 놓인 $N$개의 구간으로 이루어지며, 1번부터 $N$번까지 번호가 붙는다. 남은 일은 각 구간의 높이를 정하는 것이다.

수석 건축가는 각 구간마다 가능한 높이 두 개를 이미 골라 두었다. $i$번째 구간의 높이는 $a_i$ 또는 $b_i$이다. 따라서 가능한 경우는 $2^N$가지가 남는다.

호수 가운데 있는 작은 섬의 성에는 어려움이 따른다. 폭풍우가 치는 날에는 성이 물에 잠길 수 있다. 어떤 구간의 양쪽에 더 높은 구간이 있으면, 그 구간 위에 물이 고이고 빠지지 못한다.

첫 줄에 정수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $a_1, a_2, \dots, a_N$이 주어진다.

셋째 줄에 $N$개의 정수 $b_1, b_2, \dots, b_N$이 주어진다.

$2^N$가지 벽 모두에서 모인 물의 총량을 모두 더한 값을 $10^9 + 7$로 나눈 나머지를 정수 하나로 출력한다.

높이를 고정하면, 위치 $i$의 수위가 $h$ 이상인 것은 위치 $l$과 $r$의 높이가 모두 $h$ 이상이 되는 정수 $l \le i \le r$이 존재할 때이고, 그때만이다. 위치 $1$과 $N$의 수위는 항상 그 구간의 높이와 같고, 어느 위치의 수위든 그 구간의 높이 이상이다. 위치 $i$에 모이는 물의 양은 수위에서 구간 높이를 뺀 값이며, 총량은 위치 $1, 2, \dots, N$에 대한 합이다.

$1 \le N \le 5 \cdot 10^5$.

$1 \le a_i, b_i \le 10^9$이고, 모든 $1 \le i \le N$에 대해 $a_i \ne b_i$이다.