Code Submission Evaluation System Login

Datatähti-valmennus

Ruudukko


Task | Statistics


CSES - 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.

Jokainen ansa on eri kohdassa, ja voit lisäksi 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