Hearts

Task

Little Green Heart has gifted Little Purple Heart for Valentine's Day two arrays A and B of size $N$ which together contain the numbers from $1$ to $2 \times N$ exactly once.

Little Purple Heart performs the following operation:

1. She chooses $2$ indices l and r with $1 \leq l \leq r \leq N$.
2. She creates an array C of size $k = r - l + 1$, such that for every i with $0 \leq i < k$ she chooses either $C_i = A_{l + i}$ or $C_i = B_{l + i}$.
3. She calculates the value $\text{val}(C)$, which is equal to the number of indices i with $0 \leq i < k$ such that there is no index j with $0 \leq j < i$ and $C_j > C_i$.

Little Green Heart, being the computer scientist that he is, wants to impress Little Purple Heart by computing the sum of $\text{val}(C)$ for all the arrays $C$ that she could have constructed. Since this number can be quite large, he wants to compute it modulo $10^9 +7$. Moreover, he wants to do so for Q different operations.

Formally, given Q queries of the form $(l, r)$, $1 \leq l \leq r \leq N$, he defines S as the set of all the arrays C that Little Purple Heart could have built. Then, for each query, he wants to calculate

Your task is to help Little Green Heart impress Little Purple Heart by computing the answer to each query.

Input data

The first line of the input contains the number $N$. The second line contains $N$ numbers $A_1, A_2, \ldots, A_n$ representing the array A. The third line contains $N$ numbers $B_1, B_2, \ldots, B_n$ representing the array B. Together, these 2 arrays contain the numbers from $1$ to $2 \times N$ exactly once.

The fourth line contains the number of queries $Q$. Each of the following $Q$ lines contains 2 numbers describing a query of the form l r.

Output data

The output should contain $Q$ lines representing the answers to all queries $P(l, r)$, each on a new line, computed modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq N \leq 70 \ 000$.
• $1 \leq Q \leq 70 \ 000$.

Example 1

stdin

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

stdout

37
5

Explanation

There are 2 queries.

For the first query, we will consider the subsequences $A_3, A_4, A_5, A_6$ and $B_3, B_4, B_5, B_6$ when constructing C. Next we consider all possible options for C and sum $\text{val}(C)$. For example, for $C=[3, 8, 7, 12]$, the indexes $i=0,1,3$ have the property that there is no $0 \leq j < i$ such that $C_j>C_i$. Therefore, $\text{val}(C)=3$.

Summing $\text{val}(C)$ across all arrays C that can be constructed, we get $P(3,6)=37$.

For the second query, we can construct 4 arrays C:

$P(1,2) = \text{val}([2,10])+\text{val}([2,1])+\text{val}([11,10])+\text{val}([11,1]) = 2 + 1 + 1 + 1 = 5.$

Example 2

stdin

12
11 10 7 23 1 18 22 16 8 14 20 6
3 4 9 13 19 5 24 12 15 21 17 2
1
7 11

stdout

32

Explanation

There is one query. Computing $P(7, 11) =32$.