Тор Дээрх Замууд II

2s

512MB

2294

0%

Counting Problems

Зүүн дээд нүд нь $(1,1)$ , баруун доод нүд нь $(n,n)$ байх $n \times n$ торыг авъя.

Зүүн дээд нүднээс баруун доод нүд рүү шилжинэ. Алхам бүрт баруун тийш эсвэл доош нэг нүдэд шилжиж болно. Тор дотор $m$ урхь бас бий. Урхьтай нүд рүү шилжиж болохгүй.

Боломжит замуудын нийт тоог ол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ байна: торын хэмжээ ба урхийн тоо.

Дараа нь урхийг тодорхойлсон $m$ мөр байна. Мөр бүрт хоёр бүхэл тоо $y$ ба $x$ : урхийн байрлал.

Зүүн дээд, баруун доод нүдэнд урхь байхгүй. Мөн нэг нүдэнд хамгийн ихдээ нэг урхь байна.

Гаралтын формат

Замуудын тоог $10^9+7$ -д хуваасан үлдэгдлийг хэвлэ.

Хязгаарлалт

$1 \le n \le 10^6$
$1 \le m \le 1000$
$1 \le y,x \le n$

Жишээ

Оролт1

3 1
2 2

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...