Knight Moving

Problem code: KNGHTMOV

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+AX, v+AY) or (u+BX, v+BY) 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 i-th 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 AX, AY, BX, BY.
  • The third line contains K pair(s) of integers, each represents co-ordinate 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 (109+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
Date Added: 20-07-2012
Time Limit: 9 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, 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

the value of {Ax,Ay,Bx,By}

spandanpathak @ 1 Sep 2012 05:25 PM
the value of {Ax,Ay,Bx,By} can be negative,right?

IMP : Is the time limit not

tanujrastogi @ 1 Sep 2012 09:25 PM
IMP : Is the time limit not applicble in this contest??Solutions with time exceeded are being accepted and awarded scores. Don't we need to write efficient codes this time??

Is it guaranteed there are no

ardamose123 @ 1 Sep 2012 09:51 PM
Is it guaranteed there are no infinite amount of solutions (like cycles)?

@spandanpathak Yes, they can

hiroto_adm @ 2 Sep 2012 12:50 AM
@spandanpathak Yes, they can be negative.

@ardamose123 No, you cannot

hiroto_adm @ 2 Sep 2012 12:51 AM
@ardamose123 No, you cannot assume that. Please see Output section.

Can we assume points are

bcurcio @ 2 Sep 2012 01:13 AM
Can we assume points are distinct? Can we assume moves A and B are different?

@bcurcio No, you cannot

hiroto_adm @ 2 Sep 2012 02:02 AM
@bcurcio No, you cannot assume both of them. There is no such constraint.

I found there are bugs in the

hiroto_adm @ 2 Sep 2012 04:36 PM
I found there are bugs in the model solution, and judge data were wrong. Now judge data have been fixed, submitted codes will be rejudged soon. I'm very sorry for the inconvenience.

Is the rejudge already over?

damians @ 2 Sep 2012 05:29 PM
Is the rejudge already over?

@damians No. However you can

hiroto_adm @ 2 Sep 2012 06:28 PM
@damians No. However you can submit your submitted code once again for checking.

ok, thank you

damians @ 2 Sep 2012 06:36 PM
ok, thank you

When this contest is over, I

Sumudu @ 4 Sep 2012 10:14 AM
When this contest is over, I humbly ask that others not laugh at the very silly mistakes I made in my submissions to this problem. Glad to finally get it, but my solution is quite the c******f***

If starting and final

ksh78 @ 4 Sep 2012 03:34 PM
If starting and final position are the same (0,0) and AX, AY, BX, BY are all zeros, then it means that there is no ways or there is one way (with 0 steps). Is number of steps must be greater than 0?

@ksh78 My AC solution gives

venuswitharms @ 4 Sep 2012 03:55 PM
@ksh78 My AC solution gives neither 0 nor 1 for the test case "0 0 0 0 0 0 0" @Sumudu I hope they do laugh at mine. I deserve it.

Is it possible that (Ax,Ay) =

aurinegro @ 7 Sep 2012 01:01 AM
Is it possible that (Ax,Ay) = (Bx,By). In that case, should the moves be considered the same? I mean, for the input: 1 1 0 1 1 1 1 Should the answer be 1 or 2?

@aurinegro I have the same

darkgt @ 7 Sep 2012 12:20 PM
@aurinegro I have the same question.From the statement,your answer seems to be 1. So if that, 1 1 0 1 1 0 0 answer is 1 but not -1?

@darkgt Good observation, I

aurinegro @ 7 Sep 2012 07:35 PM
@darkgt Good observation, I hadn't thought about 1 1 0 1 1 0 0. Anyway, the statement considers that two ways are different if they have a different number of steps. So, I think the answer for your testcase should be -1.

Is move (0,0) possible?

MarioYC @ 7 Sep 2012 09:54 PM
Is move (0,0) possible?

Look at the test case

bcurcio @ 8 Sep 2012 08:59 AM
Look at the test case

Someone (either the admin or

blackBird @ 8 Sep 2012 04:27 PM
Someone (either the admin or one with an accepted solution to this problem) please confirm aurinegro's claim of 1 1 0 1 1 0 0 resulting in -1.

I haven't got AC but i also

imgpsingh @ 8 Sep 2012 09:34 PM
I haven't got AC but i also think answer should be -1 for the case mentioned... :)

Are Ax,Ay,Bx,By positive?

asklzxn2 @ 9 Sep 2012 07:56 AM
Are Ax,Ay,Bx,By positive?

if you have to go from 0,0 to

kriateive @ 9 Sep 2012 08:07 PM
if you have to go from 0,0 to 0,0 and the available moves are (0 0) and (0 0) then should i take it as infinite ways(-1) or zero ways?

If we have to go from (0, 0)

hedgefog @ 9 Sep 2012 08:50 PM
If we have to go from (0, 0) to (0, 0) and none of the available moves is (0 , 0), do we print 0 or 1? Is a path with no moves considered valid?

if you have to go from 0,0 to

kriateive @ 10 Sep 2012 03:11 AM
if you have to go from 0,0 to 5,5 and the available moves are (5 5) and (5 5) then should i take it as 2 or 1 way?

Read this carefully: Two ways

Sumudu @ 10 Sep 2012 05:44 AM
Read this carefully: 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 i-th step. This should answer all your questions!

Its a request that has been

blackBird @ 10 Sep 2012 12:39 PM
Its a request that has been many times over and over again... making it one more time ... After the contest is over, please make the judge test cases and their solution available publicly! They contribute a lot to the learning curve :) If codechef does not allow it, the author can post it on his/her blog!

Please someone with AC or

kriateive @ 10 Sep 2012 03:01 PM
Please someone with AC or admin reply... if you have to go from 0,0 to 0,0 and the available moves are (0 0) and (0 0) then should i take it as infinite ways(-1) or zero ways? stuck at some test case! getting WA!!

this is something.. the

foofoo @ 11 Sep 2012 02:37 AM
this is something.. the boundary case is much more difficult then the actual case :)

Maybe this answers your

Sumudu @ 11 Sep 2012 04:09 AM
Maybe this answers your question: moving (0, 0) does indeed count as one step. Read again the definition of distinct "ways" and you should have the answer to your question. It is not ambiguous IMO.

@Sumudu.. thanks for help..

kriateive @ 11 Sep 2012 02:11 PM
@Sumudu.. thanks for help.. My code had a stupid bug.. finally got it :)

Congrats! I wish I had spent

Sumudu @ 11 Sep 2012 02:42 PM
Congrats! I wish I had spent more time on this contest (busy week!), I got stuck on Annual Parade and now have no time to write a good solution to SimNim. Happy that I have the best time on this one though (knock on wood); that's kind of rare for me :)

SUCCESSFUL SUBMISSIONS


Fetching successful submissions