Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Ruudukko

Ruudukko


View task | Model solution | Statistics


Ruudukko

Time limit:1.00 s
Memory limit:128 MB

Ruudukon koko on $n \times n$, vasen yläkulma on $(1,1)$ ja oikea alakulma on $(n,n)$.

Tehtäväsi on kulkea ruudukon vasemmasta yläkulmasta oikeaan alakulmaan. Saat liikkua joka askeleella ruudun oikealle tai alaspäin. Lisähaasteena ruudukossa on $m$ ruutua, joissa on ansa. Et voi kulkea tällaiseen ruutuun.

Montako mahdollista reittiä on olemassa?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: ruudukon koko ja ansojen määrä.

Tämän jälkeen syötteessä on $m$ riviä, joista jokainen kuvaa yhden ansan. Rivillä on kaksi kokonaislukua $y$ ja $x$: ansan sijainti.

Voit olettaa, että ruudukon vasen yläkulma ja oikea alakulma eivät ole ansoja.

Tuloste

Tulosta reittien määrä modulo $10^9+7$.

Rajat
Esimerkki

Syöte:
3 1
2 2


Tuloste:
2