== include(page="template/taskheader" task_id="padure2") ==
Poveste şi cerinţă...
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]**).
h2. Date de intrare
Fişierul de intrare $padure2.in$ ...
Î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**.
h2. Date de ieşire
În fişierul de ieşire $padure2.out$ ...
Î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**.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 1 < **N, M** ≤ 1000000
* 1 < **C** ≤ min( **N** × **M**, 1000 )
h2. Exemplu
table(example). |_. padure2.in |_. padure2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 7 7
4
2 3
4 2
2 5
4 3
| 175
|
| 7 7
3
2 3
4 2
2 5
| 280
|
== include(page="template/taskfooter" task_id="padure2") ==
