题目大意：

　　有一个$n\times m(n,m\leq 10^9)$的网格图，从一个点可以到下一行中列数比它大的点。有$k(k\leq 2000)$个点是不能走的，问从第$1$行到第$n$行共有几种方案。

思路：

　　动态规划求出以点$i$为终点的方案数，直接$O(nm)$推显然会超时，因此我们$O(k)$可以对于每个障碍点求出组合数。组合数可以用Lucas定理求。

　　Lucas定理：$\binom{n}{m}\mod p=\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n\mod p}{m\mod p}\mod p$。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 typedef long long int64; 6 inline int getint() { 7     register char ch; 8     while(!isdigit(ch=getchar())); 9     register int x=ch^'0';10     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');11     return x;12 }13 const int mod=1000003,K=2001;14 int fact[mod],factinv[mod],f[K];15 std::pair
         
           v[K];16 void exgcd(const int &a,const int &b,int &x,int &y) {17     if(!b) {18         x=1;19         y=0;20         return;21     }22     exgcd(b,a%b,y,x);23     y-=a/b*x;24 }25 inline int inv(const int &x) {26     int ret,tmp;27     exgcd(x,mod,ret,tmp);28     return (ret%mod+mod)%mod;29 }30 int lucas(const int &n,const int &m) {31     if(n