You are given an array $A[]$ of size $N$. Now you are given $Q$ queries to be performed over this array. In each query, you are given $2$ space separated integers $L$ and $R$. For each query, you need to you need to find the summation of the xor-sum of all triplets $(i,j,k)$ of the sub-array $L...R$ , where $L \le  i < j < k \le R$.

In short, you need to find $\sum (A[i] \oplus A[j] \oplus A[k])$, over all triplets $(i,j,k)$ , such that $L \le i < j < k  \le R$ . Print the answer for each query , Modulo $10^9+7$

Input Format

The first line contains a single integer $N$.

The next line contains  array $A[]$ of $N$ integers.

The next line contains $2$ space separated integers $Q$ and $2$.

Each of the next $Q$ lines contains two space separated integers $L$ and $R$

Output Format :

Print $Q$ lines, the $i^{th}$ line denoting the answer to the $i^{th}$ query, Modulo $10^9+7$

Input Constraints :

$1 \le N,Q \le 10^5$

$1 \le A[i] \le 10^{12}$

$1 \le L \le R \le N$