J. Japanese Bands
time limit per test
3 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

Grammy is designing a new trading card game (TCG) based on her favorite Japanese music media franchise, BanG Dream!. By her design, there are $$$n_1$$$ character cards and $$$n_2$$$ music cards in total. Now she needs to assign an integer between $$$1$$$ and $$$m$$$ (both inclusive) for each card, representing the magic power it contains.

In every TCG game, there must be some certain combos that may cause extra damage. Grammy now is considering a special rule that relates to the value assigned to cards. Specifically, $$$k$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \cdots, (a_k, b_k)$$$ are chosen, satisfying $$$1 \le a_i, b_i \le m$$$. Grammy wants to make sure each of these value combos can be played in her game. Therefore, for each pair of integers $$$(a_i, b_i)$$$, the assignment must meet at least one of the two following constraints:

  • $$$a_i$$$ can be found on a character card and $$$b_i$$$ can be found on a music card.
  • $$$a_i$$$ can be found on a music card and $$$b_i$$$ can be found on a character card.

Please help Grammy count the number of valid card-value assignments.

Let $$$\mathbb{C}$$$ be the multi-set of the integers on the character card and $$$\mathbb{M}$$$ be the multi-set of the integers on the music card. We say two assignments are different if their $$$\mathbb{C}$$$s are different or their $$$\mathbb{M}$$$s are different.

Recall that an integer can appear multiple times in a multi-set. We say two multi-sets $$$\mathbb{X}$$$ and $$$\mathbb{Y}$$$ are different if there exists an integer $$$k$$$ such that the number of times $$$k$$$ appears in $$$\mathbb{X}$$$ is not equal to that in $$$\mathbb{Y}$$$.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 500$$$) indicating the number of test cases. For each test case:

The first line contains four integers $$$n_1$$$, $$$n_2$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n_1, n_2 \le 10^9$$$, $$$1 \le m \le 20$$$, $$$1 \le k \le m^2$$$).

For the following $$$k$$$ lines, the $$$i$$$-th line contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le m$$$).

It's guaranteed that there are at most $$$5$$$ test cases satisfying $$$m \gt 10$$$.

Output

For each test case output one line containing one integer indicating the number of valid card-value assignments. As the answer may be large, output the answer modulo $$$(10^9 + 7)$$$.

Example
Input
3
2 3 3 3
2 3
1 1
2 3
2 2 2 1
1 1
1 1 10 2
1 2
1 3
Output
6
4
0
Note

For the first sample test case, the valid pairs of $$$(\mathbb{C}, \mathbb{M})$$$ are $$$(\{1, 2\}, \{1, 1, 3\})$$$, $$$(\{1, 2\}, \{1, 2, 3\})$$$, $$$(\{1, 2\}, \{1, 3, 3\})$$$, $$$(\{1, 3\}, \{1, 1, 2\})$$$, $$$(\{1, 3\}, \{1, 2, 2\})$$$ and $$$(\{1, 3\}, \{1, 2, 3\})$$$.

For the second sample test case, the valid pairs of $$$(\mathbb{C}, \mathbb{M})$$$ are $$$(\{1, 1\}, \{1, 1\})$$$, $$$(\{1, 2\}, \{1, 1\})$$$, $$$(\{1, 1\}, \{1, 2\})$$$ and $$$(\{1, 2\}, \{1, 2\})$$$.