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ţă

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 cd1.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 yi ci separate printr-un spaţiu, corespunzătoare numărului de CD-uri yi, care se pun din cutia i în cutia ci, i=1, 2, ..., n.

Date de ieşire

Fişierul de ieşire cd1.out conţine o singură linie pe care va fi scris numărul k modulo 9901.

Restricţii

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

Exemple

cd1.in	cd1.out	Explicaţii
3 12 3 2 2 3 1 1	20	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.

autor: Prof. Doru Popescu Anastasiu

propunător: Prof. Emanuela Cerchez

Liceul de Informatică ″Grigore Moisil″

emanuela.cerchez@gmail.com