Set

Cerință

Se dau $X$, $P$ și $Q$.
Se consideră setul de numere naturale cu factori primi mai mici sau egali cu $X$ și exponenți până în $P$.

Se consideră și $Q$ operații de tipul $a$, $b$:

• Se elimină din set toate numerele care sunt divizibile cu $a^b$.
  
  Pentru fiecare operație se garantează că $a$ este prim și vrem după fiecare operație să calculăm câte elemente sunt în set modulo $10^9+7$.

Date de intrare

Pe prima linie se află valorile $X$, $P$ și $Q$. Pe următoarele $Q$ linii se afla câte $2$ numere $a$ și $b$.

Date de ieșire

Se vor afișa $Q$ linii, pe a $i$-a linie se va afișa numărul de elemente rămas în set după primele $i$ operații.

Restricții și precizări

• $2 \leq X,P,Q \leq 10^6$;
• $2 \leq a \leq X$
• $a$ mereu este prim
• $1 \leq b \leq P$

Exemplul 1

stdin

4 2 2
2 2
3 1

stdout

6
2

Explicație

Setul inițial este: ${1,2,3,4,6,9,12,18,36}$.
După ce eliminăm elementele divizibile cu $2^2$ rămânem cu setul ${1,2,3,6,9,18}$.
După ce eliminăm și elementele divizibile cu $3^1$ rămânem cu setul ${1,2}$.