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, …, 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ța

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 y[i] , care se pun din cutia i în cutia c[i] , i=1,2,...,n.

Date de ieșire

Fișierul de ieșire cd.out va conține pe prima linie numărul k modulo 9901.

Restricții și precizări

• 2 ≤ n ≤ 300
• În fiecare cutie sunt cel mult 1000 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.