Fişierul intrare/ieşire:	padure2.in, padure2.out	Sursă	ACM ICPC - Romanian Programming Contest 2016
Autor	Vlad Turcuman	Adăugată de	Paul Diac •diac_paul
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Padure2

Gigel a descoperit o nouă pădure de brazi în drum spre scoală. Uitându-se puţin la aceasta işi dă seama că ea este de fapt o matrice de N pe M unde în fiecare celulă se află un brad sau o ciupercă. Având un talent nativ la căţărat în copaci, Gigel vrea să afle în câte moduri poate să ajungă din [1,1] în [N,M] mergând numai prin copaci. Fiind o maimuţă în curs de evoluţie, Gigel nu stie încă să numere asa că a venit la voi şi vă roagă sa-l ajutaţi. În plus Gigel ştie să meargă doar în două direcţii: în jos (din [i,j] sare în [i+1,j]) şi în dreapta (din [i,j] sare în [i,j+1]).

Date de intrare

În fişierul padure2.in se află pe prima linie numerele N si M reprezentând punctul în care vrea să ajungă Gigel. Pe a doua linie se afla C, numărul de ciuperci. Pe fiecare dintre următoarele C linii se află perechi de forma Li Ci, reprezentand poziţia la care se află ciuperca i.

Date de ieşire

În fişierul padure2.out se va scrie numărul de posibilităţi prin care maimuţa Gigel poate să ajungă din [1,1] în [N,M] conform cerinţelor. Deoarece numărul acesta poate fi foarte mare, se cere numărul de drumuri modulo numărul prim 2000003.

Restricţii

• 1 < N, M ≤ 1000000
• 1 < C ≤ min( N × M, 1000 )

Exemplu

Cum se trimit solutii?