Fişierul intrare/ieşire:padure2.in, padure2.outSursăACM ICPC - Romanian Programming Contest 2016
AutorVlad TurcumanAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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

padure2.inpadure2.out
7 7
4
2 3
4 2
2 5
4 3
175
7 7
3
2 3
4 2
2 5
280
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?