链接: https://cses.fi/problemset/task/1078

板块: Counting Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

考虑一个 $n \times n$ 的网格，其左上角为 $(1,1)$，右下角为 $(n,n)$。

你的任务是从左上角方格移动到右下角方格。每步可以向右或向下移动一格。此外，网格中有 $m$ 个陷阱，你无法移动到有陷阱的方格上。

总共有多少条可能的路径？

输入

第一行输入包含两个整数 $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$

样例输入

3 1
2 2

样例输出

2