2333良心题，，，

不带障碍是很简单的，就是一个C(n+m,n)就是方案数，然而有了障碍怎么办呢。。。

设f[i]为走到第i个障碍点且合法的方案数。（当然，首先把这些障碍排一下序）

用类似与容斥的思想，首先让f[i]=C(a[i].x+a[i].y,a[i].x)（这里的a表示点）,然后考虑要减掉什么。

枚举之前的障碍点，那么走过这个点 j 到第 i 点的方案数就是 f[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)，那么减掉就好了。

现在考虑如果走多个障碍点呢？

然而经过一番考虑之后发现这个问题是不用考虑的。

为什么呢？因为是酱紫的，

而且C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)这部分，是 j 点到 i 点的全部路径，也就是说，包含了所有一个点，2个点在内的情况，

而我们枚举的 j 点就相当于枚举了障碍序列的开头的第一个障碍（f[j]是我们处理好了的东西， 也就是说，我们的f[j]就保证了从原点走到 j 点是没有障碍点），所以就可以枚举所有的障碍排列，也就是全部减去了。

奥妙重重2333

1 #include 
     
       2 #define LL long long 3 using namespace std; 4  5 const int mod=1000000007; 6 const int maxn=100005; 7  8 int f[maxn],inv[maxn<<1],fac[maxn<<1]; 9 int n,m,k;10 11 struct node{12     int x,y;13 }a[maxn];14 bool cmp(node a, node b) {
   return a.x==b.x?a.y
      
       
        =a[j].y) 38                 f[i]=(f[i]-(LL)C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j]%mod+mod)%mod;39     }40     cout<
        
         <