h2. Date de intrare

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.

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 perechea $x y$. 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$ va contine raspunsurile la cele $Q$ interogari. Daca raspunsul este $x / y$, se va afisa $x * inv(y) mod 1.000.000.007$.

În fişierul de ieşire $monede2.out$ se vor afisa raspunsurile la cele $Q$ interogari. Daca raspunsul este $x / y$, se vor afisa oricare numere $p q$ unde $q$ este nenul, si $x * q = y * p (mod 1.000.000.007)$.

h2. Restricţii
* $1 ≤ N ≤ 1.000.000$
* $1 ≤ Q ≤ 1.000.000$

* $1 &le; x, y < 1.000.000.007$

* Pentru $23$ de puncte, $N ≤ 15, Q ≤ 100$.
* Pentru alte $10$ puncte, $N, Q ≤ 1.000$.
* Pentru alte $37$ puncte, $N, Q ≤ 200.000$.

h2. Exemplu
table(example). |_. monede2.in |_. monede2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 6
1 4
1 3
1 2
1 1
1 2
1 3
2 2
2 3
3 3
| 1 4
5 12
1 2
1 3
1 2
1 2

|

h3. Explicaţie
 
...
 

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