题意：
给你平面上两个向量，走到指定点，一些点不能经过，求方案数
煞笔提一开始被题面带偏了一直郁闷为什么方案不是无限
现在精简的题意.....不就是$bzoj3782$原题嘛，还不需要$Lucas$了....
因为这是平面向量啊
基本定理与唯一表示.....
小新上课强调了辣么多次......
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=,M=1e6,P=1e9+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int x,y,n,x1,y1,x2,y2;
struct Point{
int x,y;
bool operator <(const Point &r)const{return x<r.x || (x==r.x && y<r.y);}
}a[N];
int m;
bool solEqu(int x,int y,Point &p){//printf("solEqu %d %d\n",x,y);
int a=x*y1-y*x1,b=x2*y1-y2*x1;//printf("a b %d %d\n",a,b);
if(a%b) return ;else p.x=a/b;
a=x*y2-y*x2,b=x1*y2-y1*x2;//printf("a b %d %d\n",a,b);
if(a%b) return ;else p.y=a/b;//printf("Point %d %d\n",p.x,p.y);
return ;
}
ll inv[M],fac[M],facInv[M];
void ini(int n){
inv[]=;fac[]=facInv[]=;
for(int i=;i<=n;i++){
if(i!=) inv[i]=(P-P/i)*inv[P%i]%P;
fac[i]=fac[i-]*i%P;
facInv[i]=facInv[i-]*inv[i]%P;
}
}
inline ll C(int n,int m){return fac[n]*facInv[m]%P*facInv[n-m]%P;}
ll f[N];
inline void modify(ll &x){if(x<) x+=P;}
void dp(){
for(int i=;i<=m;i++){
f[i]=C(a[i].x+a[i].y,a[i].x);
for(int j=;j<i;j++) if(a[j].x<=a[i].x && a[j].y<=a[i].y)
modify(f[i]-=C(a[i].x-a[j].x+a[i].y-a[j].y , a[i].x-a[j].x) * f[j] %P);
}
}
int main(){
freopen("in","r",stdin);
ini();
x=read();y=read();n=read();
x1=read();y1=read();x2=read();y2=read();
if(!solEqu(x,y,a[++m])) {puts("");return ;}
for(int i=;i<=n;i++){
x=read();y=read();
if(!solEqu(x,y,a[++m]) || a[m].x>a[].x || a[m].y>a[].y) m--;
}
sort(a+,a++m);
dp();
printf("%lld",f[m]);
}