Chiralitate

Cerință

O echipă de chimiști români a descoperit un nou tip de moleculă pe care a numit-o $poli-nucleo-arenă$. O arenă are un nucleu circular aromatic format din atomi de carbon, în schimb ce o $poli-nucleo-arenă$ are un număr $n$ de nuclei circulari concentrici, fiecare nucleu $i$ fiind format din $m[i]$ atomi ce pot fi de $k[i]$ tipuri. Din păcate, echipa s-a izbit de o mare problemă, aflarea numărului de $poli-nucleo-arene$ distincte știind numărul de nuclei si descrierea fiecărui nucleu. Echipa de chimiști vă roagă pe voi să o ajutați.
Două $poli-nucleo-arene$ $X$ și $Y$ sunt considerate distincte dacă prin rotirea nucleilor $poli-nucleo-arenei$ $X$ nu se poate ajunge la $Y$.

Date de intrare

Pe prima linie se găsește $n$, numărul de nuclei. Pe fiecare dintre următoarele n linii se găsește câte o pereche de numere ($m[i]$,$k[i]$), semnificând că nucleul $i$ este format din $m[i]$ atomi ce pot fi de $k[i]$ tipuri.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, reprezentând restul împărtirii numărului de $poli-nucleo-arene$ distincte la $1e9+7$.

Restricții și precizări

• $1 \leq n \leq \ 1000$
• $1 \leq m[i], k[i] \leq 10 \ 000$;
• NUCLEII SE POT ROTI INDEPENDENT

Exemplul 1

stdin

2
2 2
2 2

stdout

9

Explicație

Un nucleu cu 2 atomi ce pot fi de 2 tipuri are 3 configurații: (0,0), (1,0), (1,1); După cum se poate vedea (1,0) si (0,1) reprezinta același nucleu. Cum sunt 2 nuclei inseamnă că rezultatul va fi 3*3, adică 9.

Exemplul 2

stdin

2
2 2
2 3

stdout

18

Explicație

Analog exemplului 1.