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.

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.

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