Масивҳо ва Суроғаҳо

Тавсифи масъала

Ба як адади целлӣ $n$ ва як массив $a$ бо $n$ ададҳои целлӣ дода шудааст. Раванди сохтани массив $b$ ҳамчун зерин таъриф шудааст.

Аввалан, массив $b$ холӣ аст. Раванд дар $n$ давраҳои пайдарпай гузаронида мешавад. Дар давраи $i$-ум, массиви нав $b$ ҳамчун пайвастшавии версияи қаблии массиви $b$, унсури $a_i$, ва боз версияи қаблии массиви $b$ таъриф мешавад.

Формалӣ, дар ҳар давраи $i$-ум, массиви $b$ мувофиқи қоида навсозӣ мешавад:

$b := b + [a_i] + b$,

ки дар он нишонаи «$+$» пайвастшавии массивҳоро нишон медиҳад, ва $[a_i]$ массивест, ки аз як унсури $a_i$ иборат аст.

Пас аз анҷоми сохтани массиви $b$, лозим аст, ки $q$ пурсишҳоро коркард кунем. Ҳар пурсиш бо як ҷуфти ададҳои целлӣ $(l, r)$ таъриф мешавад. Барои ҳар пурсиш, лозим аст, ки ҷамъбасти унсурҳои массиви $b$ аз мавқеи $l$ то мавқеи $r$ шомили модул $$ пайдо шавад.

Формати вуруд

Дар хатти аввал, як адади целлӣ $n$ $(1 \le n \le 60)$ дода шудааст --- шумораи унсурҳои массиви $a$.

Дар хатти дуюм, $n$ ададҳо дода шудаанд $a_1, a_2, \ldots, a_n$ $$ --- унсурҳои массиви .

Дар хатти сеюм, як адади целлӣ $q$ $(1 \le q \le 2 \cdot 10^5)$ дода шудааст --- шумораи пурсишҳо.

Дар хатти баъдӣ $q$ хатҳо, ҷуфтҳои ададҳои целлӣ $l$ ва $r$ дода шудаанд $(1 \le l \le r \le 2^n - 1)$.

Формати хуруҷ

Барои ҳар пурсиш, як адади ягона бароварда мешавад --- ҷамъбасти унсурҳои массиви $b$ дар сегменти $[l, r]$ модул $10^9 + 7$. Ҳар ҷавобро дар хатти алоҳида бароварда кунед.

Натиҷа

3
2 0 5
6
1 4
1 7
3 5
6 6
3 7
4 7

9
13
9
0
11
9