老W是个棋艺高超的棋手，他最喜欢的棋子是马，更具体地，他更加喜欢马所行走的方式。老W下棋时觉得无聊，便决定加强马所行走的方式，更具体地，他有两双手，其中一双手能让马从(u,v)移动到(u+Ax,v+Ay)而另一双手能让马从(u,v)移动到(u+Bx,v+By)。小W看见老W的下棋方式，觉得非常有趣，他开始思考一个问题：假设棋盘是个无限大的二维平面，一开始马在原点(0,0)上，若用老W的两种方式进行移动，他有多少种不同的移动方法到达点(Ex,Ey)呢？两种移动方法不同当且仅当移动步数不同或某一步所到达的点不同。老W听了这个问题，觉得还不够有趣，他在平面上又设立了n个禁止点，表示马不能走到这些点上，现在他们想知道，这种情况下马有多少种不同的移动方法呢？答案数可能很大，你只要告诉他们答案模(10^9+7)的值就行。

马拦过河卒的升级版本

这里很明显得解一下aX+bY=C这样的方程，然后这样就可以转化为经典的O(X*Y)DP

但是本题X*Y巨大

我们发现如果是是不考虑的答案数

这样不妨对干涉点排序

考虑DP：

减去所有起始点到当前选择干涉点*当前跟新干涉点的组合数

#include
    
     using namespace std;	typedef int INT;#define int long long const int mod=1e9+7;const double eps=1e-8;const int N=1e6+1000;int ex,ey;int ax,ay,bx,by;int x,y;int n;double a[4][4];struct Node{	int x,y;}A[N];bool cmp (Node A,Node B){	return A.x
     
      
       eps)				id=j;		}		for(int j=1;j<=2+1;j++){			swap(a[id][j],a[i][j]);		}		if(fabs(a[i][i])
       
        =0;--i){		inv[i]=inv[i+1]*(i+1)%mod;	}}int C(int n,int m){	return fac[m]*inv[n]%mod*inv[m-n]%mod;}int ans=0;int G[511][511];int F[511];inline void Build(int &x,int &y){	    int a1,a2,b1,b2;    a1=x*by-y*bx; a2=ax*by-ay*bx;    b2=bx*ay-ax*by; b1=x*ay-ax*y; //	cout<
        
         <<" "<
         
          <<" "<
          
           <<" "<
           
            <<" "<
            
             <<" "<
             
              <<" "<
              
               <<" "<
               
                <<" "<
                
                 <<" "<
                 
                  <<'\n'; if(a2==0 || b2==0) { x=-1; y=-1; return ; } if((a1/a2)*a2!=a1 || (b1/b2)*b2!=b1) { x=-1; y=-1; return ; } int A=a1/a2,B=b1/b2; x=A; y=B;}void Graph(){ for(int i=0;i<=n;++i){ for(int j=i+1;j<=n;++j){// if(i==8&&j==9){// cout<
                  
                   <<" "<
                   
                    <<" "<
                    
                     <<" "<
                     
                      <<'\n';// cout<
                      
                       <<" "<
                       
                        <<'\n';// exit(0);// } G[i][j]=C(A[j].x-A[i].x,A[j].y-A[i].y+A[j].x-A[i].x); } }}INT main(){ cin>>ex>>ey>>n>>ax>>ay>>bx>>by; Build(ex,ey); Pre(); A[0].x=0; A[0].y=0; for(int i=1;i<=n;++i){ cin>>A[i].x>>A[i].y; // cout<
                        <<" "<
                         
                          <<" "<
                          
                           <<'\n'; Build(A[i].x,A[i].y); if(A[i].x<0||A[i].y<0||A[i].x>ex||A[i].y>ey) n--,i--; } n++;// cout<
                           
                            <<'\n'; A[n].x=ex; A[n].y=ey; sort(A+1,A+1+n,cmp); Graph(); for(int i=1;i<=n;++i){// cout<
                            
                             <<" "<
                             
                              <<'\n'; F[i]=G[0][i];// cout<
                              
                               <<'\n'; for(int j=1;j