E. Girl Permutation
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\).
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\).
For each test case, output a single integer on a separate line — the number of suitable permutations modulo \(10^9 + 7\).
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]\)