== include(page="template/taskheader" task_id="monede2") ==

Poveste şi cerinţă...

Se considera un sir de $N$ monede numerotate de la $1$ la $N$. La o aruncare, moneda $i$ are probabilitate $p[i]$ sa cada pajura, si $1 - p[i]$ sa cada cap.
 
Pentru $Q$ intervale $[a, b]$ se cere sa se afle probabilitatea ca, daca s-ar arunca cu monedele $a, a+1, ..., b$, un numar impar de monede sa pice pajura.

h2. Date de intrare

Fişierul de intrare $monede2.in$ ...

Fişierul de intrare $monede2.in$ va contine, pe primul rand, numerele $N, Q$. Pe urmatoarele $N$ randuri se vor gasi probabilitatile din sirul $p$. Daca $p[i] = x / y$, atunci al $i$-lea rand din acestea va contine numarul $x * inv(y) mod 1.000.000.007$, unde $inv(y)$ este inversul modular al lui $y$, modulo $1.000.000.007$. Pe urmatoarele $Q$ randuri se vor gasi perechi $a b$, indexate de la 1, dintre care fiecare reprezinta o interogare.

h2. Date de ieşire

În fişierul de ieşire $monede2.out$ ...

În fişierul de ieşire $monede2.out$ va contine raspunsurile la cele $Q$ interogari. Daca raspunsul este $x / y$, se va afisa $x * inv(y) mod 1.000.000.007$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ Q ≤ 1.000.000$

h2. Exemplu