Where is the Pizza?
Contest: Codeforces Round 788 (Div. 2)
Difficulty rating: 1400
Tags: data structures, dfs and similar, dsu, graphs, implementation, math

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.

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
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

Example output:
4
1
2
2
1
8
1
2
2

Editorial:
Let's first solve the version where the array $$$d$$$ is filled with $$$0$$$'s (in other words there is no constrain on the permutation $$$c$$$ that needs to be formed).
Let's say we have the permutation $$$[1,2,3,4]$$$ as $$$a$$$ and the permutation $$$[3,1,2,4]$$$ as $$$b$$$.
Suppose that we have chosen the first element of the array $$$c$$$ to be the first element of array $$$a$$$, this way we can't choose the first element of array $$$b$$$. Since we want array $$$c$$$ to be a permutation, we will have to get the first element of $$$b$$$ from $$$a$$$ (which is $$$3$$$). If we search for $$$3$$$ in array $$$a$$$ and add it to array $$$c$$$, we wont be able to choose the element of $$$b$$$ in the corresponding index (which is $$$2$$$), so we again search for $$$2$$$ in array $$$a$$$ and add it to $$$c$$$. This time, the element in $$$b$$$ at the corresponding index is $$$1$$$, which is already included in the array $$$c$$$, so we are not obliged to select another element from array a.
We observe that the elements that we were obliged to choose from $$$a$$$ along with the initial element we selected $$$[1,2,3]$$$ are a permutation of the elements at the corresponding indices of $$$b$$$ $$$[3,1,2]$$$, and for each group that has a size bigger than one we have $$$2$$$ options, either we select the whole group from $$$a$$$, or we select the whole group from $$$b$$$.
So the answer to this version is to just count the number of groups of size bigger than $$$1$$$ (let's say the number of groups is $$$p$$$) and print $$$2^p$$$.
Now what if array $$$d$$$ is not filled with $$$0$$$'s? We just have to make sure that each group we count has $$$0$$$'s in all the corresponding indices of the group we are considering, otherwise this group has only one option and we don't count it.
This solution can be implemented in many ways, but using DSU to union each group together is the most elegant way to implement it in my opinion.