2045. [CodeChef KNGHTMOV] 骑士移动

【题目描述】

考虑一张无限大的方格棋盘。我们有一个“骑士”，它必须从(0,0)格开始，按照如下规则，移动至(X,Y)格：每一步，它只能从(u,v)格移动至(u+Ax,v+Ay)或者(u+Bx,v+By)。注意，该规则可能不同于国际象棋中骑士的移动规则。

此外，棋盘上有K个障碍格，骑士不能进入这些格子。

你的任务是计算骑士有多少种到达指定位置的方案。我们认为两种方案不同，当且仅当它们的步数不同，或者存在某个i使得两种方案中，骑士在第i步到达的格子不同。注意，骑士在到达(X,Y)格后还可能继续移动。

【输入格式】

第1行1个整数T，代表测试数据组数。每组数据格式如下：

第1行3个整数X,Y,K。

第2行4个整数Ax,Ay,Bx,By。

第3行K对整数，每对都是一个障碍格的坐标。如果K=0，则这一行不存在。

【输出格式】

对每组数据，输出移动方案数模1000000007（10^9+7）的值。如果有无穷多种方案，输出-1.

【样例输入】

3

3 3 0

1 2 2 1

9 9 2

1 2 2 1

1 2 6 6

1 1 0

0 0 0 0

【样例输出】

2

4

0

【提示】

在前两个数据中，骑士的移动方式相当于国际象棋中的“骑士”，但只有两个方向。在第一个数据中，有两种方案：(0,0)->(1,2)->(3,3)和(0,0)->(2,1)->(3,3).

在第三个数据中，骑士无法移动，因此永远无法到达终点。

所有坐标的绝对值不超过500

(0,0)不是障碍格

(X,Y)不是障碍格

1<=T<=5

对于40%的数据，0<=K<=5

对于100%的数据，0<=K<=15

【来源】

Codechef Knight Moving