AND vs OR

The value of a sequence $a_l,a_{l+1},\cdots,a_r$ is defined as follows.

• If the length is 2 or less, the value of the sequence is $0$.
• If the length is 3 or more, the value of the sequence is $(a_l \, \And \, a_r) - (a_{l+1} \, | \, a_{l+2} \, | \cdots | \, a_{r-1})$.

$\And$ is the bitwise and operator, and $|$ is the bitwise or operator.

You are given a sequence of integers $a_1,a_2,\cdots,a_N$.

Write a program that processes the following query $Q$ times.

• $i$ $j$ : Find the sum of all positive values among the values of every contiguous subsequence of $a_i,a_{i+1},\cdots,a_j$, and print it. $(1\leq i \leq j \leq N)$

The first line contains an integer $N$. $(1\leq N \leq 1\,000\,000)$

The second line contains the sequence $a_1,a_2,\cdots,a_N$ as integers separated by spaces. $(0\leq a_i \leq 10^{18})$

The third line contains an integer $Q$, the number of queries. $(1\leq Q \leq 1\,000\,000)$

From the fourth line, the next $Q$ lines each contain two integers $i$ and $j$ separated by a space. $(1\leq i \leq j \leq N)$

For each query, print the answer on its own line.

Since the answer can be very large, print it modulo $10^9+7$.