E. Girl Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Some permutation of length $$$n$$$ is guessed.

You are given the indices of its prefix maximums and suffix maximums.

Recall that a permutation of length $$$k$$$ is an array of size $$$k$$$ such that each integer from $$$1$$$ to $$$k$$$ occurs exactly once.

Prefix maximums are the elements that are the maximum on the prefix ending at that element. More formally, the element $$$a_i$$$ is a prefix maximum if $$$a_i > a_j$$$ for every $$$j < i$$$.

Similarly, suffix maximums are defined, the element $$$a_i$$$ is a suffix maximum if $$$a_i > a_j$$$ for every $$$j > i$$$.

You need to output the number of different permutations that could have been guessed.

As this number can be very large, output the answer modulo $$$10^9 + 7$$$.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains three integers $$$n, m_1$$$ and $$$m_2$$$ ($$$1 \le m_1, m_2 \le n \le 2 \cdot 10^5$$$) — the length of the permutation, the number of prefix maximums, and the number of suffix maximums, respectively.

The second line of each test case contains $$$m_1$$$ integers $$$p_1 < p_2 < \ldots < p_{m_1}$$$ ($$$1 \le p_i \le n$$$) — the indices of the prefix maximums in increasing order.

The third line of each test case contains $$$m_2$$$ integers $$$s_1 < s_2 < \ldots < s_{m_2}$$$ ($$$1 \le s_i \le n$$$) — the indices of the suffix maximums in increasing order.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer on a separate line — the number of suitable permutations modulo $$$10^9 + 7$$$.

Example
Input
6
1 1 1
1
1
4 2 3
1 2
2 3 4
3 3 1
1 2 3
3
5 3 4
1 2 3
2 3 4 5
20 5 4
1 2 3 4 12
12 13 18 20
6 2 3
1 3
3 4 6
Output
1
3
1
0
317580808
10
Note

The following permutations are suitable for the second set of input data:

  • $$$[1, 4, 3, 2]$$$
  • $$$[2, 4, 3, 1]$$$
  • $$$[3, 4, 2, 1]$$$

The following permutations are suitable for the sixth set of input data:

  • $$$[2, 1, 6, 5, 3, 4]$$$
  • $$$[3, 1, 6, 5, 2, 4]$$$
  • $$$[3, 2, 6, 5, 1, 4]$$$
  • $$$[4, 1, 6, 5, 2, 3]$$$
  • $$$[4, 2, 6, 5, 1, 3]$$$
  • $$$[4, 3, 6, 5, 1, 2]$$$
  • $$$[5, 1, 6, 4, 2, 3]$$$
  • $$$[5, 2, 6, 4, 1, 3]$$$
  • $$$[5, 3, 6, 4, 1, 2]$$$
  • $$$[5, 4, 6, 3, 1, 2]$$$