dp 方程想错了。果然还是欠练啊。
如果我们不考虑坏点，那么从 (0,0) 到 (x,y) 的方案数是 c(x+y,x) 或者 c(x+y,y)。
因为有坏点的存在，我们可以逆向思维，先求出总数，然后减去那些由于坏点的影响不能走的方案数。
由于存在黑点 i(x,y)，从左上到该黑点的方案数 sum[i] = C(x+y,x)，其中如果在黑点 i 的左上还有黑点 j(u,v)，那么应该减去 sum[j]*C(x-u+y-v)(y-u)。
然后可以把坏点按照 x 为第一关键字，y 为第二关键字排序。
从左上出发，往右下扫黑点。
还有一个考点是大组合数的求法。
因为太大，递推也不行。
可以用欧拉公式求逆元的方法求解。
或者是 lucas 定理。
记得拿到骑士 (1,1) 到 (n,m) 的题和这道题很像。
也是从左上到右下，中间有些坏点，不过骑士的走法并不是向下或者向右 1 步，而是向右 p 步，向下 q 步，或者向右 q 步，向下 p 步。
而且那道题的 n 和 m 是 10^9 的数量级…
那道题的话就只能用 lucas 定理了貌似。
这道题算是那道题的弱化版本，在此 orz zhangk，果然厉害。
所以我还是决定写 lucas 定理的解法。
lucas 定理适用于求 C(n,m)%p，p 为素数且 n,m 很大的情况。
引用一段题解：
题意，给一个n * m 的网格，其只有一些点是坏的不能走，要求从0，0点起到n,m的总方案数。
设dp[i] 表示到达第i个坏点且不经过其他坏点的总方案数。增加一个点(n-1,m-1)，则dp[k]即为答案。
壮态转移方程 dp[i] = C[x[i]+y[i],x[i]) - sum(dp[j] * C(x[i] - x[j] + y[i] - y[j],x[i] - x[j]),j表示，所有在i之前的坏点，由于这里的dp[i]都是不经过别的坏点，不会有重复的路径，所以减去以前的坏点到达i的路径就是答案。先排序，就可以得到每个点的先后顺序，这样在更新状态的时候，可以从小到大枚举。总的复杂度为 o(k * k);现在剩下的问题 就是要求c(n,m)，由于n,m很大，一般求组合数的方法是n * m，这样复杂度太高，即使用递推o(n)的复杂度，也是太高的。这里引入了 定理Lucas，这个就是专门求大组合数的一种方法。Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p) 设 aa = n % p,bb = m % p；这里可以看出来把n,m很大的数转化了相对比较小的aa,bb,这个公式把n - n/p m - m/p，这样可以递归解决。求c(aa,bb)就可以直接用组合公式aa!/(bb! * (aa - bb)! )，由于这里有除法，所以要求bb! * (aa - bb)！的逆。 由欧拉公式 p为素数a的逆为pow_mod(a,p-2,p)；即a^(p-2) % p;所以整个公式转化成ret=(ret*fac[a]*pow_mod(fac[b]*fac[a-b]%p,p-2,p))%p; 这样就可以递归求解了。总的说一下，虽然这题，由于n,m很小只有10^5，所以不用lucas定理也可以解决，但有可能会出现一种情况n,m很大，达到10^9，而MoD很小，只有10^5，这样，这个lucas定理，就可以有真正的用场了，而且要求MOD是质数才可以的，因为是质数，那个欧拉定理才适用的。
代码实现
1/*************************************************************************
2 > File Name: code/cf/#313/EE.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月18日 星期二 18时43分18秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=2E3+7;
32const int mod = 1E9 + 7;
33const int M = 1E5+7;
34int h,w,n;
35typedef long long ll;
36ll fac[2*M];
37ll dp[N];
38pair<int,int> p[N];
39LL quickpow(LL a,LL b)
40{
41 LL res=1;
42 while(b)
43 {
44 if(b&1) res=res*a%mod;
45 a=(a*a)%mod;
46 b>>=1;
47 }
48 return res;
49}
50LL C(LL a,LL b)
51{
52 if(b>a) return 0;
53 return fac[a]*quickpow(fac[b]*fac[a-b]%mod,mod-2)%mod;
54}
55LL lucas(LL a,LL b)
56{
57 if(b==0) return 1;
58 return (C(a%mod,b%mod)*lucas(a/mod,b/mod))%mod;
59}
60void init()
61{
62 fac[0]=1,fac[1]=1;
63 for(int i=1;i<2*M;i++)
64 {
65 fac[i]=(fac[i-1]*i)%mod;
66 }
67}
68int main()
69{
70 init();
71 cin>>h>>w>>n;
72 for(int i=1;i<=n;i++){
73// int x,y; cin>>x>>y;
74// p[i].first=x; p[i].second=y;
75 cin>>p[i].first;
76 cin>>p[i].second;
77 }
78 p[n+1].first=h,p[n+1].second=w;
79 sort(p+1,p+n+2);
80
81 for(int i=1;i<=n+1;i++)
82 {
83 dp[i]=lucas(p[i].first+p[i].second-2,p[i].first-1);
84 for(int j=1;j<i;j++)
85 {
86 if(p[j].second<=p[i].second)
87 {
88 dp[i]-=dp[j]*lucas(p[i].first-p[j].first+p[i].second-p[j].second,p[i].first-p[j].first)%mod;
89 dp[i] = (dp[i]+ mod ) % mod;
90 }
91 }
92 }
93 cout<<dp[n+1]<<endl;
94
95 return 0;
96}