题目描述

一个登山爱好者，今天他来到了黄山。 俗话说的好，不走回头路。所以在黄山，你只能往前走，或者往上走。并且很显然的是，当你走到山脊的时候，你不能够往上走，你只能往前走一步再往上走。 抽象一点而言就是，你可以把黄山视为一个$N×N$格点图，从$(0,0)$开始出发，要走到$(N,N)$。当他走到位置$(x,y)$的时候，可以往$(x+1,y)$或$(x,y+1)$走，并且当他走到$(x,x)$的时候，由于他已经处在了山脊上，所以他不能够往$(x,x+1)$方向上走。 当他兴致勃勃准备开始爬山的时候，他的同伴告诉他，黄山由于年久失修，有一些位置出现了大坑，不能走。他觉得更刺激了，但他想先知道他能有多少种方式走到黄山顶。 由于这个数字很大，所以你只需要将答案对$10^9 + 7$取模输出即可。

输入

第一行包括两个整数$N,C$,分别表示你可以把黄山视作一个$N×N$的格点图，并且黄山上面有$C$个位置出现了大坑。 接下来的$C$行，每行包括两个整数$X,Y$,表示$X,Y$这个位置不能走。保证$X≥Y$,也就是说$(X,Y)$必然在山上。 保证这$C$个点互不相同。

输出

输出只有一个整数$Ans$，表示他爬上山顶的路径数对$10^9+7$取模的值。

输入样例

5 2
5 0
1 1

输出样例

27

提示

【样例输入2】

7 4
6 5
5 3
2 1
7 1

【样例输出2】

34

【数据规模与约定】 对于30%的数据，保证$N≤5000$。 对于另外20%的数据，保证$C=0$。 对于另外20%的数据，保证$C=1$。 对于100%的数据，保证$N≤100000,C≤1000$。 保证对于$(0,0),(N,N)$不存在障碍点。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。