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 \)
$$ (1 \oplus 2 \oplus 3)+(2 \oplus 3 \oplus 4)+(1 \oplus 2 \oplus 4)+(1 \oplus 3 \oplus 4)=18 $$