dakara

Dacii liberi și-au ascuns comoara în una dintre cele $N$ camere ale cetății. Fiecare cameră este păzită de un loial slujitor. Te-ai infiltrat în cetate cu scopul de a găsi comoara, așa că începi să bați la uși.

Dacă ai bate la ușa $i$, slujitorul ți-ar spune dacă comoara se află într-o cameră din stânga camerei $i$, din dreapta camerei $i$ sau chiar în camera $i$. Slujitorul este om bun, dar o mică atenție îl va face să-și aducă mai bine aminte unde se află comoara, așa că îl vei răsplati complet voluntar cu $2^{P_i}$ kosoni. De vreme ce vrei să oferi o experiență unică fiecărui slujitor, valorile $P_i$ vor forma o permutare a mulțimii $\{1, \dots, N\}$.

Pentru ca totul să meargă fără probleme, îți imaginezi $Q$ scenarii de tipul: “Dacă comoara se găsește în intervalul de camere $[l, r]$, care ar fi numărul minim de kosoni pe care îi voi oferi slujitorilor, în cel mai rău caz, pentru a găsi comoara?”. De vreme ce răspunsul poate să fie foarte mare, se cere restul său la împărțirea cu $10^9 + 7$.

Date de intrare

Pe prima linie se află numerele $N$ și $Q$. Pe următoarea linie se află $N$ numere naturale nenule distincte. Pe următoarele $Q$ linii se găsesc câte două numere $l_i$, $r_i$ reprezentând scenariul $i$.

Date de ieșire

Se vor afișa $Q$ linii, pe linia $i$ se va găsi răspunsul pentru cel de-al $i$-lea scenariu, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N, Q \leq 200 000$
• $1 \leq P_i \leq N$
• Șirul $P$ este o permutare.
• $1 \leq l_i \leq r_i \leq N$
• Pentru $3$ puncte: $1 \leq N, Q \leq 50$
• Pentru $6$ puncte: $1 \leq N, Q \leq 200$
• Pentru $23$ de puncte: $1 \leq N, Q \leq 1000$
• Pentru $51$ de puncte: $1 \leq Q \leq 100$
• Pentru $16$ puncte: Fără restricții suplimentare

Exemple

Exemplul 1

Intrare

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

Ieșire

70
64
68

Exemplul 2

Intrare

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

Ieșire

168
0
128