Grid Paths II

题目描述

考虑一个 n \times n 的网格，其左上角方格为 (1,1)，右下角方格为 (n,n)。 你的任务是从左上角方格移动到右下角方格。每一步你可以向右或向下移动一个方格。此外，网格中有 m 个陷阱。你不能移动到有陷阱的方格。 可能的路径总数是多少？

输入格式

第一行输入包含两个整数 n 和 m：网格的大小和陷阱的数量。 随后有 m 行描述陷阱。每一行包含两个整数 y 和 x：一个陷阱的位置。 你可以假设左上角和右下角没有陷阱。

输出格式

输出路径数对 $10^9+7$ 取模后的结果。

3 1
2 2

2

提示

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

标签: CSES1078|计数问题

来源

CSES1078|计数问题