DOJ1 - DOJO Corridor I

There's a long rectangular corridor in the hall's dojo, one place is already taken by a magic hanjō (1×1 square). You have to put tatamis (1×2 rectangle) in order to cover exactly the rest of the corridor. Sometimes it's possible, sometimes not!

Input

The input begins with the number T of test cases in a single line. In each of the next T lines there are two integers : N, M the size of the corridor, I,J coordinates of the magic hanjō, and K the modulo for the output.

Output

For each test case, print the number of possibility to do the job, modulo K.

Example

Input:
3
1 3 1 3 100
2 3 2 2 100
3 7 1 3 100

Output:
1
0
56

Corridor

Constraints

1 <= T <= 30000

1 <= N <= 4

1 <= M <= 10^9

1 <= I <= N

1 <= J <= M

1 <= K <= 10^9

Uniform, independent, random input in the range.

Time limit is set to allow one half kB of python3 code to get AC.

Edit(19/I/2015, after cluster switch) : now my old code ends in 0.16s using PY3.4.

Edit(11-2-2017, after compiler update) : new TL. My old code ends in 0.09s using PY3.5.


Added by:Francky
Date:2012-07-06
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2015-08-07 13:19:19 Dénes Ferenc
Solved two very different ways and I got WA, the two solutions give the same answers for all random input. Also checked with several known inputs, and the results are reasonable. Can one post some test input/output pairs. Thanks

=(Francky)=> No other test case is provided ; thanks for your comprehension and good luck.

Last edit: 2015-08-07 13:57:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.