Unirea pentru Performanta XI-XII 2024 | fuziune

Armata albastră a primit sarcina de a proteja legendarele cuburi ale dragonului. Pentru a le face treaba mai ușoară, aceștia au primit două inele fermecate cu abilitatea de a fuziona luptătorii care le poartă. Când $2$ luptători fuzionează, puterea luptătorului rezultat este egală cu suma celor două puteri inițiale, la care se adaugă produsul acestora. Formal, dacă cei doi luptători au puterile $a$ respectiv $b$, atunci după fuzionare vor avea puterea $a + b + a * b$. Generalul Abelius are nevoie ajutorul vostru pentru a testa puterea armatei albastre.

Cerință

Se dă un vector format din $N$ numere naturale reprezentând puterile luptătorilor din armata albastră, și $Q$ interogări formate din câte o pereche de numere naturale $s_i$ și $d_i$. Vi se cere să aflați puterea luptătorilor din intervalul $[s_i, d_i]$, dacă aceștia ar fuziona folosind inelele fermecate. Fuzionarea acestora se face în ordinea indicilor, de la stânga la dreapta: cei doi luptători cei mai din stânga fuzionează, apoi rezultatul fuzionează cu cel de-al 3-lea etc.

Date de intrare

Pe prima linie a fișierului de intrare fuziune.in se găsesc $2$ numere $N$ și $Q$ reprezentând numărul de luptători din armata albastră, respectiv numărul de interogări ale generalului Abelius.
Pe a doua linie se vor găsi $N$ numere naturale $a_i$, fiecare reprezentând puterea luptătorului de pe poziția $i$.
Pe următoarele $Q$ linii se vor găsi $Q$ perechi de numere naturale $s_i$ și $d_i$, câte o pereche pe câte o linie, reprezentând capetele intervalului pentru cea de-a $i$-a interogare.

Date de ieșire

În fișierul de ieșire fuziune.out se vor găsi $Q$ numere, fiecare pe câte o linie, cel de-al $i$-lea număr reprezentând răspunsul la cea de-a $i$-a interogare. Deoarece rezultatul poate fi foarte mare se cere afișarea acestuia modulo $10^9+7$.

Restricții și precizări

• $1 \leq N, Q \leq 1 \ 000 \ 000$;
• $1 \leq s_i \leq d_i \leq N$;
• $1 \leq a_i \leq 1 \ 000 \ 000 \ 000$;

Exemplul 1

fuziune.in

10 5
2 5 7 3 1 3 5 6 9 2
1 4
3 5
8 10
5 5
4 7

fuziune.out

575
63
209
1
191

Explicație

Pentru prima interogare pornim de la intervalul $[1, 4]$, format din elementele $\{2, 5, 7, 3\}$.
Prima fuziune: $2 + 5 + 2 * 5 = 17$.
Elementele din interval devin $\{17, 7, 3\}$.
A doua fuziune: $17 + 7 + 17 * 7 = 143$.
Elementele devin $\{143, 3\}$.
A treia fuziune: $143 + 3 + 143 * 3 = 575$.
Rezultatul pentru prima interogare este $575$.