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 \)