C. Где пицца?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хоссам в попытках найти пиццу наткнулся на две перестановки $$$a$$$ и $$$b$$$ длины $$$n$$$.

Вспомним, что перестановкой называется массив из $$$n$$$ различных чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, а $$$[1,2,2]$$$ — не перестановка ($$$2$$$ встречается дважды), и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве есть число $$$4$$$).

Хоссам позабыл про пиццу и начал играть с этими перестановками. В процессе игры некоторые элементы первой перестановки смешались с элементами второй, но к удивлению Хоссама в итоге получилась тоже перестановка длины $$$n$$$.

Более конкретно, он смешал перестановки, получив массив $$$c$$$ следующим образом.

  • Для всех $$$i$$$ ($$$1\le i\le n$$$), он сделал $$$c_i=a_i$$$ или $$$c_i=b_i$$$.
  • Массив $$$c$$$ является перестановкой.

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

Гарантируется, что существует хотя бы одна перестановка $$$c$$$, удовлетворяющая всем ограничениям.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 10^5$$$) — длину перестановок.

Следующая строка содержит $$$n$$$ различных чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$) — первую перестановку.

Следующая строка содержит $$$n$$$ различных чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_i\le n$$$) — вторую перестановку.

Следующая строка содержит $$$n$$$ целых чисел $$$d_1,d_2,\ldots,d_n$$$ ($$$d_i$$$ равно $$$0$$$, $$$a_i$$$, или $$$b_i$$$) — описание известных значений $$$c$$$. Если $$$d_i=0$$$, то про значение $$$c_i$$$ ничего не известно. Иначе $$$c_i=d_i$$$.

Гарантируется, что существует хотя бы одна перестановка $$$c$$$, удовлетворяющая всем ограничениям.

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

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

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

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

В первом наборе входных данных подходят $$$4$$$ перестановки: $$$[2,3,1,4,5,6,7]$$$, $$$[2,3,1,7,6,5,4]$$$, $$$[2,3,1,4,6,5,7]$$$, $$$[2,3,1,7,5,6,4]$$$.

Во втором наборе входных данных подходит только одна перестановка: $$$[1]$$$.

В третьем наборе входных данных подходят $$$2$$$ перестановки: $$$[6,5,2,1,4,3]$$$, $$$[6,5,3,1,4,2]$$$.

В четвертом наборе входных данных подходят $$$2$$$ перестановки: $$$[1,2,8,7,4,3,6,5]$$$, $$$[1,6,4,7,2,3,8,5]$$$.

В пятом наборе входных данных подходит только одна перестановка: $$$[1,9,2,3,4,10,8,6,7,5]$$$.