E. Девочка-перестановочка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Загадана какая-то перестановочка длины $$$n$$$.

Вам даны индексы её префиксных максимумов и суффиксных максимумов.

Напомним, что перестановка длины $$$k$$$ — это такой массив размера $$$k$$$, что в нем встречается каждое целое число от $$$1$$$ до $$$k$$$ ровно один раз.

Префиксные максимумы — элементы, которые являются максимумом на префиксе, заканчивающемся в этом элементе. Более формально, элемент $$$a_i$$$ является префиксным максимумом, если $$$a_i > a_j$$$ для каждого $$$j < i$$$.

Аналогично определяются суффиксные максимумы, элемент $$$a_i$$$ является суффиксным максимумом, если $$$a_i > a_j$$$ для каждого $$$j > 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$$$.

Пример
Входные данные
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
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]$$$