cd

Ionică a strâns foarte multe CD-uri cu jocuri, muzică, filme, etc. pe care le are aşezate în $n$ cutii, codificate prin $1, 2, \dots, n$. Pe la Ionică vine în vizită vărul lui, Florin, care tocmai câştigase un concurs de matematică. Ca să-i mai taie din elan, Ionică îi propune lui Florin să pună o parte din CD-uri într-o ladă mai mare, astfel încât să se ia din fiecare cutie cel puţin câte un CD şi la sfârşit să rămână în fiecare cutie cel puţin un CD.
Pentru a complica problema, Ionică nu îi spune lui Florin câte CD-uri sunt în fiecare cutie, ci îi spune că are în total $S$ CD-uri şi că, dacă ia din fiecare cutie un număr de CD-uri şi le pune în altă cutie va obţine în final acelaşi număr de CD-uri în toate cutiile.

Cerinţă

Să se scrie un program care cunoscând $n$, $S$ şi numărul de CD-uri mutate din fiecare cutie, determină numărul $k$ de modalităţi distincte de introducere a CD-urilor în ladă, respectând regula din enunţ.

Date de intrare

Fişierul de intrare cd.in conţine pe prima linie numerele naturale $n$ şi $S$ separate printr-un spaţiu, iar pe următoarele $n$ linii perechile de numere naturale $y_i \ c_i$ separate printr-un spaţiu, corespunzătoare numărului de CD-uri yi, care se pun din cutia $i$ în cutia $c_i, i = 1, 2, \dots, n$.

Date de ieşire

Fişierul de ieşire cd.out conţine pe prima linie numărul $k$ modulo $9 \ 901$.

Restricţii şi precizări

• $2 \leq n \leq 300$
• În fiecare cutie sunt cel mult $1 \ 000$ CD-uri.
• $k$ modulo $p$ reprezintă restul împărţirii lui $k$ la $p$
• $S$ modulo $n = 0$
• O modalitate de alegere a CD-urilor ce vor fi puse în ladă diferă de o altă modalitate, dacă din cel puţin o cutie se alege un număr diferit de CD-uri.

Exemplu

cd.in

3 12
3 2
2 3
1 1

cd.out

20

Explicaţie

Se obţine faptul că în prima cutie sunt $6$ CD-uri, în a doua $3$ CD-uri, iar în a treia $3$ CD-uri.