26098번 - 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$로 나눈 나머지를 출력한다.