7271. 网格路径 II (Grid Paths II)
时间限制：1000 MS 内存限制：256 MB
题目描述
时间限制：1.00 s 空间限制：512 MB ## 题目描述 考虑一个 $n \times n$ 的网格，其左上角方格为 $(1,1)$，右下角方格为 $(n,n)$。 你的任务是从左上角移动到右下角。在每一步中，你只能向右或向下移动一格。此外，网格中存在 $m$ 个陷阱。你不能移动到含有陷阱的方格。 问可能路径的总数是多少？ ## 输入格式 输入的第一行包含两个整数 $n$ 和 $m$：网格的大小和陷阱的数量。 接下来有 $m$ 行描述陷阱。每行包含两个整数 $y$ 和 $x$，表示一个陷阱的坐标。 你可以假设左上角和右下角方格中没有陷阱。你也可以假设每个方格最多只有一个陷阱。 ## 输出格式 输出路径总数对 $10^9+7$ 取模后的结果。 ## 输入输出样例 ### 输入 #1 ```text 3 1 2 2 ``` ### 输出 #1 ```text 2 ``` ## 说明/提示 ### 数据规模与约定 * $1 \le n \le 10^6$ * $1 \le m \le 1000$ * $1 \le y,x \le n$