CF1670C.Where is the Pizza?

While searching for the pizza, baby Hosssam came across two permutations $a$ and $b$ of length $n$.

Recall that a permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Baby Hosssam forgot about the pizza and started playing around with the two permutations. While he was playing with them, some elements of the first permutation got mixed up with some elements of the second permutation, and to his surprise those elements also formed a permutation of size $n$.

Specifically, he mixed up the permutations to form a new array $c$ in the following way.

• For each $i$ ($1\le i\le n$), he either made $c_i=a_i$ or $c_i=b_i$.
• The array $c$ is a permutation.

You know permutations $a$, $b$, and values at some positions in $c$. Please count the number different permutations $c$ that are consistent with the described process and the given values. Since the answer can be large, print it modulo $10^9+7$.

It is guaranteed that there exists at least one permutation $c$ that satisfies all the requirements.

在寻找披萨的过程中，小 Hosssam 偶然发现了两个长度为 $n$ 的排列 $a$ 和 $b$。

回忆一下，一个排列是由 $1$ 到 $n$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

小 Hosssam 忘记了披萨，开始摆弄这两个排列。在他摆弄的过程中，第一个排列中的一些元素与第二个排列中的一些元素混在了一起，令他惊讶的是，这些混在一起的元素也构成了一个长度为 $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$。

The first line contains an integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 10^5$) — the length of the permutations.

The next line contains $n$ distinct integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$) — the first permutation.

The next line contains $n$ distinct integers $b_1,b_2,\ldots,b_n$ ($1\le b_i\le n$) — the second permutation.

The next line contains $n$ distinct integers $d_1,d_2,\ldots,d_n$ ($d_i$ is either $0$, $a_i$, or $b_i$) — the description of the known values of $c$. If $d_i=0$, then there are no requirements on the value of $c_i$. Otherwise, it is required that $c_i=d_i$.

It is guaranteed that there exists at least one permutation $c$ that satisfies all the requirements.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print the number of possible permutations $c$, modulo $10^9+7$.

对于每个测试用例，输出可能的排列数 $c$ 对 $10^9+7$ 取模的结果。

In the first test case, there are $4$ distinct permutation that can be made using the process: $[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]$.

In the second test case, there is only one distinct permutation that can be made using the process: $[1]$.

In the third test case, there are $2$ distinct permutation that can be made using the process: $[6,5,2,1,4,3]$, $[6,5,3,1,4,2]$.

In the fourth test case, there are $2$ distinct permutation that can be made using the process: $[1,2,8,7,4,3,6,5]$, $[1,6,4,7,2,3,8,5]$.

In the fifth test case, there is only one distinct permutation that can be made using the process: $[1,9,2,3,4,10,8,6,7,5]$.

在第一个测试用例中，使用该过程可以生成 $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$ 个不同的排列：$[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$ 个不同的排列：$[1,9,2,3,4,10,8,6,7,5]$。