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 dynamicprog gausselim numbertheory sep12 
Date Added:  20072012 
Time Limit:  9 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
the value of {Ax,Ay,Bx,By}
IMP : Is the time limit not
Is it guaranteed there are no
@spandanpathak Yes, they can
@ardamose123 No, you cannot
Can we assume points are
@bcurcio No, you cannot
I found there are bugs in the
Is the rejudge already over?
@damians No. However you can
ok, thank you
When this contest is over, I
If starting and final
@ksh78 My AC solution gives
Is it possible that (Ax,Ay) =
@aurinegro I have the same
@darkgt Good observation, I
Is move (0,0) possible?
Look at the test case
Someone (either the admin or
I haven't got AC but i also
Are Ax,Ay,Bx,By positive?
if you have to go from 0,0 to
If we have to go from (0, 0)
if you have to go from 0,0 to
Read this carefully: Two ways
Its a request that has been
Please someone with AC or
this is something.. the
Maybe this answers your
@Sumudu.. thanks for help..
Congrats! I wish I had spent