1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
| #include "iostream" #include "algorithm" #include "cstring" #include "cstdio" #include "cmath" #include "vector" #include "map" #include "set" #include "queue" using namespace std; #define MAXN 1000006
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i) #define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i) #define pii pair<int,int> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back #define vi vector<int> #define all(x) (x).begin() , (x).end() #define mem( a ) memset( a , 0 , sizeof a ) typedef long long ll; #define P 1000000007 int n , m , ex , ey , ax , ay , bx , by; pii poi[MAXN]; int J[MAXN] , iJ[MAXN]; int Pow( int x , int a ) { int ret = 1; while( a ) { if( a & 1 ) ret = 1ll * ret * x % P; x = 1ll * x * x % P , a >>= 1; } return ret; } inline int det( int a , int b , int c , int d ) { return ( a * d - b * c ); } int t; inline int wkr( int X , int Y , int& a , int& b ) { a = det( X , bx , Y , by ) , b = det( ax , X , ay , Y ); if( a % t || b % t ) return 0; a /= t , b /= t; return 1; } int f[MAXN]; int A[MAXN] , B[MAXN]; int wy( int x , int y ) { return J[x + y] * 1ll * iJ[x] % P * iJ[y] % P; } void solve() { J[0] = 1; rep( i , 1 , MAXN - 1 ) J[i] = 1ll * J[i - 1] * i % P; iJ[MAXN - 1] = Pow( J[MAXN - 1] , P - 2 ); per( i , MAXN - 2 , 0 ) iJ[i] = 1ll * iJ[i + 1] * ( i + 1 ) % P; cin >> ex >> ey >> n; cin >> ax >> ay >> bx >> by; t = det( ax , bx , ay , by ); rep( i , 1 , n ) { scanf("%d%d",&poi[i].fi,&poi[i].se); wkr( poi[i].fi , poi[i].se , poi[i].fi , poi[i].se ); } poi[n + 1] = mp( ex , ey ); wkr( poi[n + 1].fi , poi[n + 1].se , poi[n + 1].fi , poi[n + 1].se ); sort( poi + 1 , poi + n + 1 ); int x , y; rep( i , 1 , n + 1 ) { x = poi[i].fi , y = poi[i].se; if( x < 0 || y < 0 ) continue; f[i] = wy( x , y ); if( !f[i] ) continue; rep( j , 1 , i - 1 ) if( f[j] && x >= poi[j].fi && y >= poi[j].se ) { f[i] += P - 1ll * f[j] * wy( x - poi[j].fi , y - poi[j].se ) % P , f[i] %= P; } } cout << f[n + 1] << endl; }
signed main() {
solve(); }
|