Description

恶梦是一个登山爱好者，今天他来到了黄山。

俗话说的好，不走回头路。所以在黄山，你只能往前走，或者往上走。并且很显然的是，当你走到山脊的时候，你不能够往上走，你只能往前走一步再往上走。

抽象一点而言就是，你可以把黄山视为一个N * N格点图，恶梦从(0,0)开始出发，要走到(N,N)。当他走到位置(x,y)的时候，它可以往(x + 1,y),或(x,y+1)走。

并且当他走到(x,x)的时候，由于他已经处在了山脊上，所以他不能够往(x,x+1)方向上走。

当恶梦兴致勃勃准备开始爬山的时候，他的同伴告诉他，黄山由于年久失修，有一些位置出现了大坑，不能走。恶梦觉得更刺激了，但他想先知道他能有多少种方式走到黄山顶。

由于这个数字很大，所以你只需要将答案对10^9 + 7取模输出即可。

 

Input

第一行包括两个整数N,C,分别表示你可以把黄山视作一个N * N的格点图，并且黄山上面有C个位置出现了大坑。

接下来的C行，每行包括两个整数X,Y,表示X,Y这个位置不能走。保证X>=Y,也就是说(X,Y)必然在山上。

保证这C个点互不相同。

Output

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

 

Sample Input

输入1： 5 2 5 0 1 1 输入2： 7 4 6 5 5 3 2 1 7 1

Sample Output

输出1： 27 输出2： 34

 

Data Constraint

对于30%的数据,保证N<=5000

对于另外20%的数据，保证C=0

对于另外20%的数据，保证C=1

对于100%的数据，保证N<=100000,C<=1000

保证对于(0,0),(N,N)不存在障碍点。

 

题解

• 题目大意：给定c个不能走的点，问从（0,0）到（n,n）不经过不能走的点和y>x的点的路径数量
• 首先30%的数据，很容易直接n^2dp就好了f[i][j]=f[i-1][j]+f[i][j-1]
• 考虑一下反过来做，ans=全部的路径-不合法的路径
• 显然我们可知道从(0,0)到(x,y)的无限制的路径数=C(x+y,x)
• 那么现在就来考虑一下不合法的路径数
• 先考虑一下没有山脊限制的情况，设f[i]表示走到第i个路障的方案数（不经过其他的路障）
• 那么f[i]可以从其他路障的f[j]转移容斥过来得到，就是在经过第j个路障时容斥掉不合法的路径数
• 再考虑一下有山脊的限制，对于从(a,b)要走到(c,d)，那么不碰到对称轴的方案数=所有走到(c,d)的方案数-所有走到(c,d)关于对称轴对称的对称点的方案数
• 就按照上面的方法做就好了，完结（撒花）

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define ll long long 5 using namespace std; 6 const int N=100010,mo=1e9+7; 7 int n,c; 8 ll f[N],g[N],fac[2*N],ny[2*N],r; 9 struct edge { ll x,y; }a[N];10 ll ksm(ll a,ll b) { for (r=1;b;b>>=1,a=a*a%mo) if (b&1) r=r*a%mo; return r; }11 ll C(int b,int a) 12 { 13     if (a==0||a==b) return 1;14     return ((fac[b]*ny[a])%mo*ny[b-a])%mo; 15 }16 bool cmp(edge a,edge b) { return a.x