Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
115 - The 12th Zhejiang University Programming Contest - B
Flipping the Board

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Alice likes to play a game called "Flipping the Board". In the game, there is a sufficiently large board whose upper-left coner is (1, 1) and the grid in the i-th row and j-th column is (i, j). There is another board the player can control which is of size R*C placed in the position covering (1, 1) to (R, C). The player can flip the board on one of its four edges. Since the board is placed parallel to the edges of the larger board, it covers another R*C grids every time after being flipped.

Here is an example of flipping where R=2, C=3. The board is placed initially on the position of the red rectangle. After flipping on its right edge, it becomes the green one and then after flipping on its lower edge, it becomes the purple one. The grid on (1, 1) also covers (1, 6) and (4, 6) after each flipping.

Players will also paint the 2*R*C grids on board(on both sides) before flipping. After flipping, the corresponding grids on the larger board will be stamped on the same color.

After certain times of flipping, grids (1, 1) to (R0, C0) are all stamped with some colors. Then Alice comes up with a question. How many different patterns can the area of (1, 1) to (R0, C0) be? But this seems to be too simple. So three restrictions are added.

  1. The colors on both sides of a grid should be the same.
  2. Colors of some grids are already given.
  3. Colors in grid (i, j) and (i + 1, j) are different for i ∈ [1 .. R-1] and j ∈ [1 .. C].

Since the result can be very large, print the answer modulo 1,000,000,007.

Note: In the case the given grids conflict, the answer is 0.

Input

There are multiple test cases. The first line contains an integer T (T ≤ 10) indicating the number of test cases. Then T test cases follow.

For each test case, the first line contains six integers R0, C0, R, C, n and m (1 ≤ R0, C0 ≤ 1012, 1 ≤ R, C ≤ 108, 0 ≤ n ≤ 105, 1 ≤ m ≤ 108, RR0, CC0), where n is the number of grids of which color is already known and m is the number of colors available to be used to paint each of the grids. The next n lines each containing three integers ri, ci and colori (1 ≤ riR0, 1 ≤ ciC0, 1 ≤ colorim, (ri, ci) ≠ (rj, cj)) indicating the known grids.

Output

For each case, print one integer, the number of different patterns modulo 1,000,000,007.

Sample Input

2
10 13 3 5 3 7
2 1 5
2 2 4
2 3 3
10 13 3 5 3 7
2 1 5
8 9 4
2 3 3

Sample Output

962842610
962842610

Author: ZHUANG, Junyuan
Submit    Status