CSES1078 网格路径
#CS1078. 网格路径
网格路径
题目背景
翻译自 CSES-1078 题。
题目描述
考虑一个 n×nn \times nn×n 的网格，其中左上角的格子是 (1,1)(1, 1)(1,1)，右下角的格子是 (n,n)(n, n)(n,n)。
你的任务是从左上角的格子移动到右下角的格子。在每一步中，你可以向右或向下移动一个格子。此外，网格中有 m 个陷阱，你不能移动到含有陷阱的格子。
你需要计算从左上角到右下角的所有可能路径的总数。
输入格式
第一行包含两个整数 n 和 m：分别表示网格的大小和陷阱的数量。
接下来的 m 行每行描述一个陷阱的位置，每行包含两个整数 y 和 x，表示陷阱的位置为 (y,x)(y, x)(y,x)。
你可以假设左上角 (1,1)(1, 1)(1,1) 和右下角 (n,n)(n, n)(n,n) 处没有陷阱。
输出格式
输出一个整数：表示从左上角到右下角的路径数量，结果对 109+710^9 + 7109+7 取模。
样例
3 1
2 2
2
说明/提示
1≤n≤106；