9120: Non-Puzzle: The Lost Array

You have just lost an integer array $a$ of length $n$. You only remember that the array satisfies the following conditions:

• 1≤ai≤m1 \leq a_{i} \leq m1≤ai≤m.

•  For some pairs of (u,v)(u,v)(u,v), au≠va_{u} \neq vau=v.

•  For some pairs of (u,v)(u,v)(u,v), numu≠vnum_{u} \neq vnumu=v, where numunum_{u}numu represents the number of occurrences of number $u$. For example, if $a=\{1,3,3,2,4\}$, then num3=2num_{3} = 2num3=2, num1=1num_{1} = 1num1=1, num2=1num_{2} = 1num2=1, num4=1num_{4} = 1num4=1.

Also, you remember an extra information: there is an array $B$ of length $m$, such that after sorting the array [num1,num2…numm][num_{1},num_{2} \dots num_{m}][num1,num2…numm] in non-decreasing order, it will become $B$.

Please calculate the number of possible arrays under these constraints. Since the answer might be huge, output the answer modulo 109+710^9 + 7109+7.

There are multiple test cases.
The first line contains the number of test cases $T$ (1≤T≤161 \le T \le 161≤T≤16). The description of the test cases follows.
The first line of each test case contains four integers $n$, $m$, $x$, $y$ ($1\le n\le 16,1\le m\le 30$, 0≤x≤nm,0≤y≤(n+1)m0\le x \le nm , 0\le y \le (n+1)m0≤x≤nm,0≤y≤(n+1)m), representing the length of the array, the upper bound of the numbers, and the number of two types of constraints.
The following line contains $m$ integers, representing B1,B2…BmB_{1},B_{2} \dots B_{m}B1,B2…Bm (0≤B1≤B2⋯≤Bm≤n0 \le B_{1}\le B_{2} \dots \le B_{m} \le n0≤B1≤B2⋯≤Bm≤n, ∑Bi=n\sum{B_{i}} = n∑Bi=n).
Each of the following $x$ lines contains two integers u,vu,vu,v(1≤u≤n,1≤v≤m1\leq u \le n, 1\le v \le m1≤u≤n,1≤v≤m), representing the constraint au≠va_{u} \neq vau=v.
Each of the following $y$ lines contains two integers u,vu,vu,v(1≤u≤m,0≤v≤n1 \le u \le m, 0 \le v \le n1≤u≤m,0≤v≤n), representing the constraint numu≠vnum_{u} \neq vnumu=v.
Some constraints might be the same. It is guaranteed that the sum of $n$ does not exceed $16$.

For each test case, output a single integer, representing the answer modulo 109+710^9 + 7109+7.

3
2 4 1 1
0 0 1 1
2 3
3 2
4 5 2 1
0 0 1 1 2
2 5
3 5
5 4
10 30 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 3

9
228
288459008