Sevenkplus was interested in contributing a challenge to hackerrank and he came up with this problem.

You are given a linear congruence system with n variables and m equations:
a₁₁ x₁ + a₁₂ x₂ + ... + a_1n x_n = b₁ (mod p)
a₂₁ x₁ + a₂₂ x₂ + ... + a_2n x_n = b₂ (mod p)
...
a_m1 x₁ + a_m2 x₂ + ... + a_mn x_n = b_m (mod p)

where,

p is a prime number
0 <= a_ij < p
0 <= x_i < p
0 <= b_i < p

Given integers n, m, p, a, b, count the number of solutions to this equation. Since the output can be large, please output your answer modulo 10^9+7.

He writes the standard solution and a test data generator without difficulty, and generates some test data. However, when he attempts to remove hidden folders from the problem folder before uploading, he accidentally deletes the input file. Luckily, the output file remains and he still remembers some features of the input. He remembers n, m, p and that w entries of a are zero. However, he cannot recall more about the input.

He wants to count how many possible inputs are there that will result in the desired output S (number of solutions to the equation system) output modulo 10^9+7. Can you help Sevenkplus?

Input Format
The first line contains an integer T. T testcases follow. For each test case, the first line contains five numbers, m, n, p, S, w. separated by a single space.
w lines follow. Each line contains two numbers x, y, which indicates that a_xy=0.

Output Format
For each test case, output one line in the format Case #t: ans, where t is the case number (starting from 1), and ans is the answer.

Constraints
1 ≤ T ≤ 33
1 <= m, n <= 1000
p <= 10^9, p is a prime number
0 <= S < 10^9+7
w <= 17
1 <= x <= m
1 <= y <= n
In any test case, one pair (x, y) will not occur more than once.

Sample Input

6
2 2 2 0 1
1 1
2 2 2 1 1
1 1
2 2 2 2 1
1 1
2 2 2 3 1
1 1
2 2 2 4 1
1 1
488 629 183156769 422223791 10
350 205
236 164
355 8
3 467
355 164
350 467
3 479
72 600
17 525
223 370

Sample Output

Case #1: 13
Case #2: 8
Case #3: 10
Case #4: 0
Case #5: 1
Case #6: 225166925

Explanation

For test case 1, the 13 possible equations are:

a11 a12 b1  a21 a22 b2
0   0   0   0   0   1
0   0   1   0   0   0
0   0   1   0   0   1
0   0   1   0   1   0
0   0   1   0   1   1
0   0   1   1   0   0
0   0   1   1   0   1
0   0   1   1   1   0
0   0   1   1   1   1
0   1   0   0   0   1
0   1   0   0   1   1
0   1   1   0   0   1
0   1   1   0   1   0

Timelimits
Timelimits for this challenge is given here