Knight Moving

All submissions for this problem are available.
Consider an infinitely large chess table.
From the cell (0, 0), our knight has to move to the cell (X, Y) by the rule:
our knight could only move from a cell (u, v) to the cell (u+A_{X}, v+A_{Y}) or (u+B_{X}, v+B_{Y}) in one move.
Note that it may be different from ordinary knight's move of chess.
In addition, there is K blocked cell(s) on the table where the knight could not move on.
Your task is to count how many distinct ways the knight could complete his mission.
Two ways are called "distinct" if and only if they have different numbers of steps or there exists i such that they are in different cells after ith step.
Note that our knight may continue to move after he reaches the cell (X, Y).
Input
The first line contains an integer T, denoting the number of test cases. Each test case is described as follows:
 The first line contains 3 integer X, Y, K.
 The second line contains 4 integers A_{X}, A_{Y}, B_{X}, B_{Y}.
 The third line contains K pair(s) of integers, each represents coordinate of a blocked cell. This line does not exist if K = 0.
Output
For each test case, output on a line the number of ways found modulo 1000000007 (10^{9}+7).
If there are infinitely many ways, then output 1 instead.
Constraints
1 ≤ T ≤ 5
0 ≤ K ≤ 15
The absolute values of all other input values are at most 500.
(0, 0) is not a blocked cell.
(X, Y) is not a blocked cell.
Example
Input: 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 Output: 2 4 0
Explanations:
In the first and second examples, our knight's move is the similar to ordinary knight's, but only 2 directions are allowed. In the first example, there are 2 ways (0, 0) > (1, 2) > (3, 3) and (0, 0) > (2, 1) > (3, 3).
In the third example, our knight's cannot move toward, so our knight's cannot complete his mission.
Author:  AnhDQ 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/KNGHTMOV 
Tags  anhdq, dynamicprogramming, gausselim, numbertheory, sep12 
Date Added:  20072012 
Time Limit:  0.9 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions