311188: CF1946E. Girl Permutation

E. Girl Permutationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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$.

ExampleInput

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

题目大意：
E. 女孩排列

给定一个长度为 $ n $ 的排列，以及它的前缀最大值和后缀最大值的下标。

定义：
- 长度为 $ k $ 的排列是一个大小为 $ k $ 的数组，其中每个整数从 $ 1 $ 到 $ k $ 恰好出现一次。
- 前缀最大值是指在其前缀结束于此元素的元素中最大的元素。形式上，如果对于所有 $ j < i $，都有 $ a_i > a_j $，则 $ a_i $ 是前缀最大值。
- 类似地，后缀最大值定义为，如果对于所有 $ j > i $，都有 $ a_i > a_j $，则 $ a_i $ 是后缀最大值。

你需要输出可能被猜测的不同排列的数量。

由于这个数字可能非常大，所以输出答案对 $ 10^9 + 7 $ 取模。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含三个整数 $ n, m_1 $ 和 $ m_2 $ ($ 1 \le m_1, m_2 \le n \le 2 \cdot 10^5 $) —— 排列的长度，前缀最大值的数量和后缀最大值的数量。

每个测试用例的第二行包含 $ m_1 $ 个整数 $ p_1 < p_2 < \ldots < p_{m_1} $ ($ 1 \le p_i \le n $) —— 前缀最大值的下标，按升序排列。

每个测试用例的第三行包含 $ m_2 $ 个整数 $ s_1 < s_2 < \ldots < s_{m_2} $ ($ 1 \le s_i \le n $) —— 后缀最大值的下标，按升序排列。

保证所有测试用例的 $ n $ 值之和不超过 $ 2 \cdot 10^5 $。

输出数据格式：
对于每个测试用例，输出一行一个整数 —— 可能的排列数量对 $ 10^9 + 7 $ 取模。题目大意： E. 女孩排列 给定一个长度为 $ n $ 的排列，以及它的前缀最大值和后缀最大值的下标。 定义： - 长度为 $ k $ 的排列是一个大小为 $ k $ 的数组，其中每个整数从 $ 1 $ 到 $ k $ 恰好出现一次。 - 前缀最大值是指在其前缀结束于此元素的元素中最大的元素。形式上，如果对于所有 $ j < i $，都有 $ a_i > a_j $，则 $ a_i $ 是前缀最大值。 - 类似地，后缀最大值定义为，如果对于所有 $ j > i $，都有 $ a_i > a_j $，则 $ a_i $ 是后缀最大值。 你需要输出可能被猜测的不同排列的数量。 由于这个数字可能非常大，所以输出答案对 $ 10^9 + 7 $ 取模。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试用例的数量。然后是测试用例的描述。 每个测试用例的第一行包含三个整数 $ n, m_1 $ 和 $ m_2 $ ($ 1 \le m_1, m_2 \le n \le 2 \cdot 10^5 $) —— 排列的长度，前缀最大值的数量和后缀最大值的数量。 每个测试用例的第二行包含 $ m_1 $ 个整数 $ p_1 < p_2 < \ldots < p_{m_1} $ ($ 1 \le p_i \le n $) —— 前缀最大值的下标，按升序排列。 每个测试用例的第三行包含 $ m_2 $ 个整数 $ s_1 < s_2 < \ldots < s_{m_2} $ ($ 1 \le s_i \le n $) —— 后缀最大值的下标，按升序排列。 保证所有测试用例的 $ n $ 值之和不超过 $ 2 \cdot 10^5 $。 输出数据格式： 对于每个测试用例，输出一行一个整数 —— 可能的排列数量对 $ 10^9 + 7 $ 取模。