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 X_i Y_i(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.

Restricţii

• 0 <= N <= 1000
• 0 <= coordonatele carteziene ale calculatoarelor <= 1 000 000 000

Exemple

bdotcom.in	bdotcom.out	Explicaţie
2 3 3 1 1 2 2	4	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)

prof. Dana Lica

C. N. "I.L.Caragiale" Ploiesti

danal182001@yahoo.com