P14196 [ICPC 2024 Hangzhou R] Japanese Bands

Grammy is designing a new trading card game (TCG) based on her favorite Japanese music media franchise, $\textit{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}$.

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 > 10$.

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)$.

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\})$.