Codeforces Round 936 (Div. 2) |
---|
Finished |
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.
Each test consists of several test cases. The first line contains a single integer t (1≤t≤104) — 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 (1≤m1,m2≤n≤2⋅105) — 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 (1≤pi≤n) — the indices of the prefix maximums in increasing order.
The third line of each test case contains m2 integers s1<s2<…<sm2 (1≤si≤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⋅105.
For each test case, output a single integer on a separate line — the number of suitable permutations modulo 109+7.
61 1 1114 2 31 22 3 43 3 11 2 335 3 41 2 32 3 4 520 5 41 2 3 4 1212 13 18 206 2 31 33 4 6
1 3 1 0 317580808 10
The following permutations are suitable for the second set of input data:
The following permutations are suitable for the sixth set of input data:
Name |
---|