
ZOJ Problem Set  3592
Alice likes to play a game called "Flipping the Board". In the game, there is a sufficiently large board whose upperleft coner is (1, 1) and the grid in the ith row and jth 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 (R_{0}, C_{0}) are all stamped with some colors. Then Alice comes up with a question. How many different patterns can the area of (1, 1) to (R_{0}, C_{0}) be? But this seems to be too simple. So three restrictions are added.
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.InputThere 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 R_{0}, C_{0}, R, C, n and m (1 ≤ R_{0}, C_{0} ≤ 10^{12}, 1 ≤ R, C ≤ 10^{8}, 0 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10^{8}, R ≤ R_{0}, C ≤ C_{0}), 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 r_{i}, c_{i} and color_{i} (1 ≤ r_{i} ≤ R_{0}, 1 ≤ c_{i} ≤ C_{0}, 1 ≤ color_{i} ≤ m, (r_{i}, c_{i}) ≠ (r_{j}, c_{j})) indicating the known grids. OutputFor each case, print one integer, the number of different patterns modulo 1,000,000,007. Sample Input2 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 Output962842610 962842610 Author: ZHUANG, Junyuan Contest: The 12th Zhejiang University Programming Contest 