Fişierul intrare/ieşire:	monede2.in, monede2.out	Sursă	InfoPro, Runda 1, Grupa A
Autor	Tamio-Vesa Nakajima	Adăugată de	Mihaela Cismaru •MihaelaCismaru
Timp execuţie pe test	1.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Monede2

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.

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 perechea x y. Pe urmatoarele Q randuri se vor gasi perechi a b, indexate de la 1, dintre care fiecare reprezinta o interogare.

Date de ieşire

Î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).

Restricţii

• 1 ≤ N ≤ 1.000.000
• 1 ≤ Q ≤ 1.000.000
• 1 ≤ 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.
• Pentru alte 15 puncte, p[i] este diferit de 1 / 2.

Exemplu

Cum se trimit solutii?