【题目大意】

sps有左手和右手，他的左手能让他的马的坐标从$(x, y)$变成$(x+ax, y+ay)$，他的右手能让他的马的坐标从$(x, y)$变成$(x+bx, y+by)$，他的马初始在$(0, 0)$，有$n$个奇怪的格子不能通行。求他的马到$(endx, endy)$的方法数，模$10^9+7$。给定$ax, ay, bx, by, endx, endy, n$以及不能通过的格子的坐标。

$ n \leq 500, -500 \leq ax, bx, ay, by, endx, endy \leq 500, ay \times bx \not= ax \times by$

【题解】

首先把左右手看做基，重新坐标化，题目就变成了，向右走一格或向下走一格。

首先$(a, b)$到$(c, d)$的方案数为$C(c-a+d-b, c-a)$。

然后设$f_i$表示$i$到终点不经过任何障碍的方案数，$w_i$表示$i$到终点没有限制的方案数，$x_{i,j}$表示障碍$i$到障碍$j$的方案数。$f_i = w_i - \sum x_{i,j} \times f_j$

随便转移转移啦！

# include <stdio.h>
# include <algorithm>
# include <iostream>

using namespace std;

typedef long long ll;
const ll mod = 1e9+7;
int n, endx, endy, ax, ay, bx, by, x[510], y[510], ex, ey;
ll X[510][510], f[510], inv[1000010], fac[1000010];
int nx[510], ny[510];

inline bool relabel(int &x, int &y, int a, int b) {
	int fz1 = a*by-b*bx, fm1 = ax*by-ay*bx, fz2 = a*ay-b*ax, fm2 = bx*ay-ax*by;
	if(fz1 % fm1 != 0 || fz2 % fm2 != 0) return false;
	x = fz1/fm1, y = fz2/fm2;
	if(x < 0 || y < 0) return false;
	return true;
}

inline ll power(ll a, int b) {
	ll s=1;
	while(b) {
		if(b&1) s=s*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return s;
}

inline ll C(int a, int b) {
	return fac[a] * inv[b] % mod * inv[a-b] % mod;
}

// (a, b) -> (c, d)
inline ll getr(int a, int b, int c, int d) {
	if(c<a || d<b) return 0ll;
	return C(c+d-a-b, c-a);
}

int main() {
	freopen("hands.in", "r", stdin);
	freopen("hands.out", "w", stdout);
	fac[0] = inv[0] = 1;
	for (int i=1; i<=1000000; ++i) {
		fac[i] = fac[i-1] * i % mod;
		inv[i] = power(fac[i], mod-2);
	}
	scanf("%d%d%d", &endx, &endy, &n);
	scanf("%d%d%d%d", &ax, &ay, &bx, &by);
	for (int i=1; i<=n; ++i) 
		scanf("%d%d", &nx[i], &ny[i]);
	
	if(relabel(ex, ey, endx, endy) == 0) {
		puts("0");
		return 0;
	}
	
	//printf("ok 1\n");
	int tn=0;
	for (int i=1; i<=n; ++i) {
		int newx, newy;
		if(relabel(newx, newy, nx[i], ny[i])) {
			if(newx > ex || newy > ey) continue;
			++tn;
			x[tn]=newx, y[tn]=newy;
		}
	}
	
	//printf("ok 2\n");
	n = tn;
	for (int i=1; i<=n; ++i)
    	for (int j=i+1; j<=n; ++j)
    		if(x[i] > x[j] || (x[i] == x[j] && y[i] > y[j])) {
    			swap(x[i], x[j]);
    			swap(y[i], y[j]);
			}
	
	//printf("ok 3\n");
	/*
	printf("============================\n");
	for (int i=1; i<=n; ++i) 
		printf("newx = %d, newy = %d\n", x[i], y[i]);
	printf("============================\n");
	*/
	
	for (int i=1; i<=n; ++i) {
		f[i] = getr(x[i], y[i], ex, ey);
		for (int j=i+1; j<=n; ++j) 
			X[i][j] = getr(x[i], y[i], x[j], y[j]);
	}
	
	//printf("ok 4\n");
	for (int i=n; i>=1; --i) {
		for (int j=i+1; j<=n; ++j) {
			f[i] = (f[i] - X[i][j] * f[j] % mod);
			if(f[i] < 0) f[i] += mod;
		}
	}
	
	//printf("ok 5\n");
	//printf("ex = %d, ey = %d\n", ex, ey);
	ll ans = getr(0, 0, ex, ey);
	//printf("ok 6\n");
	//cout << "ans = " << ans << endl;
	for (int i=1; i<=n; ++i) {
		ll tmp = getr(0, 0, x[i], y[i]);
	//	cout << tmp << ' ' << f[i] << endl;
		tmp = tmp * f[i] % mod;
		ans = ans - tmp;
		if(ans < 0) ans += mod;
	}
	
	//printf("ok 7\n");
	if(ans < 0) ans += mod;
	cout << ans << endl;
	return 0;
}
/*
4 4 1
0 1 1 0
2 3
70
*/