Avem la dispoziţie o reţea de calculatoare în care fiecare calculator este identificat printr-o pereche de numere naturale care reprezintă poziţia lui în sistemul cartezian. Serverul se află plasat în punctul de coordonate (0,0) şi fiecare punct de coordonate naturale conţine un calculator legat la reţea.
Un mesaj circulă unidirecţional, de la un calculator de coordonate (x,y) către unul dintre cele aflate pe coodonatele (x+1, y) sau (x, y+1). Există însă şi calculatoare defecte care nu pot comunica cu celelalte.
Cerinţă
Scrieţi un program care determină în câte modalităţi se poate transmite un mesaj pornind de la server la un calculator de coordonate date. Deoarece numărul poate fi destul de mare, se cere afişarea modulo 10 007 a acestuia.
Date de intrare
Fişierul de intrare bdotcom.in conţine pe prima linie numărul natural N reprezentând numărul de calculatoare defecte. Pe a doua linie perechea de numere naturale A B reprezentând coordonatele carteziene ale calculatorului destinaţie. Pe următoarele N linii, perechile de coordonate Xi Yi(1<=i<=n), reprezentând coordonatele carteziene ale calculatoarelor defecte.
Date de ieşire
Fişierul de ieşire bdotcom.out va conţine o singură linie pe care va fi scris un singur număr reprezentând restul modulo 10 007 a numărului de modalităţi determinate.
Mesajul poate traversa unul dintre drumurile: (0,0)->(1,0)->(2,0)->(3,0)->(3,1)->(3,2)->(3,3)
(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)
(0,0)->(1,0)->(2,0)->(2,1)->(3,1)->(3,2)->(3,3)
(0,0)->(0,1)->(0,2)->(1,2)->(1,3)->(2,3)->(3,3)