Massivlar va So'rovlar

Masala tavsifi

Berilgan butun son $n$ va $n$ ta butun sonlardan iborat $a$ massiv. $b$ massivini qurish jarayoni quyidagicha aniqlanadi.

Dastlab, $b$ massivi bo'sh. Jarayon $n$ ketma-ket raundda amalga oshiriladi. $i$-chi raundda, yangi $b$ massivi avvalgi $b$ massivining birikmasi, $a_i$ elementi va yana avvalgi $b$ massivining birikmasi sifatida aniqlanadi.

Rasmiy ravishda, har bir $i$-chi raundda, $b$ massivi quyidagi qoidaga muvofiq yangilanadi:

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

bu yerda «$+$» belgisi massivlarning birikmasini anglatadi, va $[a_i]$ bitta elementdan iborat massivdir.

$b$ massivini qurish jarayoni tugagach, $q$ so'rovlarni qayta ishlash zarur. Har bir so'rov juft butun sonlar $(l, r)$ bilan aniqlanadi. Har bir so'rov uchun, $b$ massivining $l$-dan $r$-gacha bo'lgan elementlarining yig'indisini ${}^{}$ ga modulyatsiya qilish talab etiladi.

Kirish formati

Birinchi qatorda, butun son $n$ $(1 \le n \le 60)$ berilgan --- $a$ massividagi elementlar soni.

Ikkinchi qatorda, $n$ ta butun son berilgan $a_1, a_2, \ldots, a_n$ $$ --- massivining elementlari.

Uchinchi qatorda, butun son $q$ $(1 \le q \le 2 \cdot 10^5)$ berilgan --- so'rovlar soni.

Keyingi $q$ qatorlarda, juft butun sonlar $l$ va $r$ berilgan $(1 \le l \le r \le 2^n - 1)$.

Chiqish formati

Har bir so'rov uchun, bitta sonni chiqarish kerak --- $b$ massivining $[l, r]$ segmentidagi elementlar yig'indisi $10^9 + 7$ ga modulyatsiya qilingan holda. Har bir javobni alohida qatorga chiqarish kerak.

Ballash

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

9
13
9
0
11
9