有一个 $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$。