Sum of Water Accumulation Over All Wall Configurations

You are given a wall consisting of \(N\) segments. For the \(i\)-th segment, its height can be chosen as either \(a_i\) or \(b_i\). Thus, there are \(2^N\) possible wall configurations. For a configuration \(h = [h_1, h_2, \ldots, h_N]\), after it rains the water accumulation at index \(i\) is defined as follows.

Let the water level at index \(i\) be \(H\) such that there exist indices \(l\) and \(r\) with \(l \le i \le r\) satisfying \(h_l \ge H\) and \(h_r \ge H\), and \(H\) is the maximum possible value with this property. Equivalently, one may compute \[ L_i = \max\{h_1, h_2, \ldots, h_i\}, \quad R_i = \max\{h_i, h_{i+1}, \ldots, h_N\} \] so that \(H = \min(L_i, R_i)\). The water accumulated at index \(i\) is \(\max(0,\min(L_i,R_i)-h_i)\).

Your task is to compute the sum of the total water accumulated over all \(2^N\) configurations and output the answer modulo \(10^9+7\).

Example: For \(N = 10\) and chosen wall heights \(4, 2, 1, 8, 6, 2, 7, 1, 2, 3\) (as shown in the image below), the actual water level becomes \(4, 4, 4, 8, 7, 7, 7, 3, 3, 3\) respectively.

inputFormat

The first line contains an integer \(N\) representing the number of wall segments.\n

The second line contains \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\).

The third line contains \(N\) space-separated integers \(b_1, b_2, \ldots, b_N\).

It is guaranteed that \(1 \le N \le 15\) so that a brute force solution over \(2^N\) configurations is feasible.

outputFormat

Output a single integer, the sum of the total water accumulated over all possible configurations, taken modulo \(10^9+7\).

sample

2
1 2
2 3

0