Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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 ai is a prefix maximum if ai>aj for every j<i.

Similarly, suffix maximums are defined, the element ai is a suffix maximum if ai>aj 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 109+7.

Input

Each test consists of several test cases. The first line contains a single integer t (1t104) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains three integers n,m1 and m2 (1m1,m2n2105) — 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 m1 integers p1<p2<<pm1 (1pin) — the indices of the prefix maximums in increasing order.

The third line of each test case contains m2 integers s1<s2<<sm2 (1sin) — 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 2105.

Output

For each test case, output a single integer on a separate line — the number of suitable permutations modulo 109+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]