C. Головоломка маленького Алана
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время перерывов в подготовке к Международной олимпиаде школьников по информатике маленький Алан любит решать различные головоломки, чтобы развивать мозги. Сегодня он решает головоломку, которая выглядит как таблица $$$2 \times n$$$, где в каждом ряду записана перестановка чисел $$$1,2,3,\ldots,n$$$.

Задача головоломки — сделать так, чтобы ни в каком ряду и ни в каком столбце не было двух одинаковых чисел (назовем такие состояния решенными), а единственная разрешенная операция — поменять местами два числа в одном столбце. Когда маленький Алан решил головоломку много раз, он заскучал и начал размышлять, а сколько вообще существует различных решенных состояний в данной головоломке, которые он может получить из некоторого начального решенного состояния, применяя только разрешенные операции?

Маленький Алан не справился с этой сложной задачей, поэтому он попросил вас помочь ему. Найдите ответ по модулю $$$10^9+7$$$.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$).

Следующие две строки описывают начальное состояние головоломки. Каждая строка содержит перестановку чисел $$$1,2,3,\ldots,n$$$, и числа в каждом столбце и в каждой строке различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество решенных состояний головоломки, которые можно получить из данного, меняя местами числа в столбцах. Так как ответ может быть большим, выведите его по модулю $$$10^9+7$$$.

Пример
Входные данные
2
4
1 4 2 3
3 2 1 4
8
2 6 5 1 4 3 7 8
3 8 7 5 1 2 4 6
Выходные данные
2
8
Примечание

Два возможных решенный состояния в примере $$$1$$$:

  • $$$[1,4,2,3]$$$ в первой строке, и $$$[3,2,1,4]$$$ во второй,
  • $$$[3,2,1,4]$$$ в первой строке, и $$$[1,4,2,3]$$$ во второй.