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
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(1122017, after compiler update) : new TL. My old code ends in 0.09s using PY3.5.
hide comments
Dénes Ferenc:
20150807 13:19:19
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

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