Nosaukums
Taciņas (tacinas)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
75%

Definīcija

Dots NxM rūtiņu laukums, no kura K rūtiņas ir izgrieztas. Uzrakstiet programmu, kas aprēķina dažādo ceļu skaitu, kā var nokļūt no rūtiņas (1,1) uz rūtiņu (N,M), ja katrā gājienā no rūtiņas (A,B) atļauts iet vai nu uz rūtiņu (A+1,B), vai uz rūtiņu (A,B+1) (ja tās nav izgrieztas).

Zināms, ka rūtiņas (1,1) un (N,M) nav izgrieztas.


Ievaddatu raksturojums

Pirmajā rindā dotas skaitļu N, M un K vērtības (1 ≤ N,M ≤ 1000, 0 ≤ K ≤ 50000). Katrā no nākamajām K faila rindām dotas vienas izgrieztās rūtiņas koordinātas.


Izvaddatu raksturojums

Vienīgajā rindā jāizvada viens vesels skaitlis - atlikums, ko iegūst, dažādo ceļu skaitu izdalot ar 1 000 000 000.


Paraugdati

Stdin
2 10 1
2 9
Stdout
1

Stdin
3 3 0
Stdout
6

Stdin
3 3 1
2 2
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.