路径计数2

题目描述

有一个 $n * n$ 的网格，有些格子是可以通行的，还有 $m$ 个格子是障碍。

一开始你在左上角的位置，你可以每一步往下或者往右走，问有多少种走到右下角的方案。

由于答案很大，输出对 $10^9+7$ 取模的结果。

输入格式

第一行两个数字 $n$, $m$。

接下来 $m$ 行，每行 $2$ 个整数 $x_i , y_i$，代表第 $i$ 个障碍的坐标。

输出格式

一个数，表示答案。

样例输入

2 1
2 1

样例输出

1

数据范围

所有数据保证 $1\leq n\leq 10^6,1 \leq m \leq 3000,1 \leq x_i,y_i \leq n$。