AND vs OR

수열 $a\_l,a\_{l+1},\cdots,a\_r$의 가치는 다음과 같이 정의된다.

• 길이가 $2$ 이하일 경우 수열의 가치는 $0$이다.
• 길이가 $3$ 이상일 경우 수열의 가치는 $(a\_l \\, \And \\,a\_r) - (a\_{l+1} \\, | \\, a\_{l+2} \\, | \cdots | \\, a\_{r-1})$로 정의된다.

$\And$연산자는 bitwise and 연산자이고, $|$연산자는 bitwise or 연산자이다.

정수로 이루어진 수열 $a\_1,a\_2,\cdots,a\_N$이 주어진다.

다음과 같은 쿼리를 $Q$번 수행하는 프로그램을 작성해보자.

• $i$ $j$ $:$ $a\_i,a\_{i+1},\cdots,a\_j$이란 수열의 모든 연속된 부분 수열의 가치 중에서 양수인 것들의 합을 구해서 출력한다. $(1\leq i \leq j \leq N)$

첫째 줄에 정수 $N$이 주어진다. $(1\leq N \leq 1\\,000\\,000)$

둘째 줄에 정수로 이루어진 수열 $a\_1,a\_2,\cdots,a\_N$이 공백으로 구분되어 주어진다. $(0\leq a\_i \leq 10^{18})$

셋째 줄에 쿼리의 개수를 나타내는 정수 $Q$가 주어진다. $(1\leq Q \leq 1\\,000\\,000)$

넷째 줄부터 $Q$개의 줄에 걸쳐 쿼리를 나타내는 두 정수 $i,j$가 공백으로 구분되어 주어진다. $(1\leq i \leq j \leq N)$

매 쿼리마다 정답을 한 줄에 하나씩 출력한다.

단, 정답이 너무 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.