← 返回题目列表

Codeforces · 1946/E

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$$$ 为模。

示例

输入 #1

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

输出 #1

1
3
1
0
317580808
10

注意

以下排列适用于第二组输入数据:

- $$$[1, 4, 3, 2]$$$
- $$$[2, 4, 3, 1]$$$
- $$$[3, 4, 2, 1]$$$

以下排列适用于第六组输入数据:

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