Girl Permutation
Contest: Codeforces Round 936 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, dp, math, number theory

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 format:
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 format:
For each test case, output a single integer on a separate line — the number of suitable permutations modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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]$$$

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

Example output:
1
3
1
0
317580808
10

Editorial:
First, if $$$p_1$$$ is not equal to $$$1$$$, or $$$s_{m_2}$$$ is not equal to $$$n$$$, or $$$p_{m_1}$$$ is not equal to $$$s_1$$$, then the answer is $$$0$$$ for obvious reasons. Otherwise, we know exactly where the number $$$n$$$ is located, at position $$$s_1$$$. Next, we have $$$\binom{n - 1}{s_1 - 1}$$$ ways to divide the numbers from $$$1$$$ to $$$n - 1$$$ into two sets — the numbers that will be in the left part and the numbers that will be in the right part (the left part — all indices $$$< s_1$$$, the right part — all indices $$$> s_1$$$). We solve for the left part, and similarly for the right part. For the left part, the position of the maximum ($$$p_{m_1 - 1}$$$) is again defined, and the maximum itself is also unique in the set of numbers for the left part, so we can again divide the left part into two, with $$$\binom{p_{m_1} - 2}{p_{m_1 - 1} - 1}$$$ ways to do so, but we can also arrange the numbers between indices $$$p_{m_1 - 1}$$$ and $$$p_{m_1}$$$ (non-inclusive) in any order, i.e., $$$(p_{m_1} - p_{m_1 - 1} - 1)!$$$ ways. Then we solve similarly for the left set (i.e., for indices less than $$$p_{m_1 - 1}$$$).