Problem 4: kinderjoy

Cerință

După ce ai terminat ultimul sezon din serialul momentului, Stranger Things, te-ai regăsit într-un vid sufletesc din care e greu să ieși. Totuși, pentru a mai diminua durerea sfârșitului, te-ai gândit să imortalizezi pentru totdeauna acest serial prin obținerea figurinelor din ultima colecție Kinder Joy x Stranger Things, însă rapid ți-ai dat seama că este mai greu decât pare.

Dorind neapărat să ai setul complet, ai început să te documentezi și ai aflat că poți identifica figurinele după coduri. Astfel, se consideră un șir de $N$ elemente $a$ , unde fiecare element reprezintă un cod posibil de pe un produs Kinder Joy. De asemenea, sursele tale mai mult sau mai puțin legale îți spun că pentru fiecare personaj $i$ din cele $Q$ totale, codul cu cea mai mare probabilitate este minimul din intervalul $[st_i, dr_i]$ , unde $st_i$ și $dr_i$ reprezintă indici din șirul $a$ .

După ce ai reușit să termini toată colecția, un prieten îți spune că echipa HackTheArt oferă un stand personalizat pentru toate figurinele dacă reușești să găsești codul X corect, bazat pe șirul codurilor cu cele mai mari probabilități calculat anterior, denumit în continuare $ans$ . Codul X este definit drept al $Q$ -lea termen al șirului $x$ , dat de formula:

\begin{cases} E_1 = x_1 = ans_1 \\ x_i = \text{ans}_i^{E_{i-1}} & \text{pentru } i \geq 2 \\ E_i = E_{i-1} + x_i & \text{pentru } i \geq 2 \end{cases}

Pentru că acest număr poate fi foarte mare, se cere afișarea lui modulo $10^9 + 7$ . Ce mai aștepți? Ai toate informațiile necesare să termini colecția ca un adevărat profesionist, dă-i drumul!

Date de intrare

Pe prima linie se găsește numărul $N$ , reprezentând numărul de coduri posibile de pe produsele Kinder Joy.
Pe a doua linie se găsesc elementele șirului $a$ , separate prin câte un spațiu.
Pe a treia linie se găsește numărul $Q$ , reprezentând numărul total de figurine.
Pe următoarele $Q$ linii se găsesc intervalele de forma $[st_i, dr_i]$ cu semnificația din enunț, intervalul $i$ aflându-se pe linia $i + 3$ .

Date de ieșire

Pe ecran se va afișa codul X.

Restricții și precizări

$1 \leq N \leq 10^6$ ;
$1 \leq a_i \leq 10^9$ ;
$1 \leq Q \leq 10^5$ ;
$1 \leq st_i \leq dr_i \leq N$ , cu $1 \leq i \leq Q$ .

Exemplul 1

stdin

stdout

Exemplul 2