题目背景

翻译自 CSES-1078 题。

题目描述

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

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

你需要计算从左上角到右下角的所有可能路径的总数。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示网格的大小和陷阱的数量。

接下来的 $m$ 行每行描述一个陷阱的位置，每行包含两个整数 $y$ 和 $x$，表示陷阱的位置为 $(y, x)$。

你可以假设左上角 $(1, 1)$ 和右下角 $(n, n)$ 处没有陷阱。

输出格式

输出一个整数：表示从左上角到右下角的路径数量，结果对 $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$