猜测长度 $$$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]$$$