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-----

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-----

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


-----Examples-----

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
Output
4
1
2
2
1
8
1
2
2


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

Source: codeforces | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Implementation

Mathematics

Spanning trees

Data structures


Solutions:
import sys
DEBUG = False

def check(a, b, c):
	a = [0] + a
	b = [0] + b
	c = [0] + c
	m_ = [0] * len(a)
	m = [0] * len(a)
	for i in range(1, len(b)):
		m_[b[i]] = i
	for i in range(1, len(a)):
		m[i] = m_[a[i]]
	total_num = 1
	used = [False] * len(m)
	for i in range(1, len(m)):
		if not used[i]:
			j = i
			c_zeros = True
			while not used[j]:
				if c[j] != 0:
					c_zeros = False
				used[j] = True
				j = m[j]
			used[i] = True
			if c_zeros and m[i] != i:
				total_num = total_num * 2 % 1000000007
	print(total_num)

def main(f):
	t = int(f.readline())
	for i in range(t):
		n = int(f.readline())
		a = list(map(int, f.readline().split()))
		b = list(map(int, f.readline().split()))
		c = list(map(int, f.readline().split()))
		check(a, b, c)
if DEBUG:
	f = open('input.txt', 'r')
else:
	f = sys.stdin
main(f)
f.close()


import sys
input = sys.stdin.readline

def find_cycles(A, B, N):
	visited = [False] * N
	nxt = dict(zip(A, B))
	seen = set()
	cycles = []
	for a in A:
		if a in seen:
			continue
		i = a
		c = []
		while i not in seen:
			seen.add(i)
			c.append(i)
			i = nxt[i]
		cycles.append(c)
	return cycles

def count(cycle, known):
	if any((c in known for c in cycle)):
		return 1
	elif len(cycle) == 1:
		return 1
	else:
		return 2

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	D = list(map(int, input().split()))
	cycles = find_cycles(A, B, N)
	known = {i for i in D if i != 0}
	ans = 1
	for c in cycles:
		ans *= count(c, known)
		ans %= 1000000007
	return ans
for _ in range(int(input())):
	print(solve())


import sys

def ri():
	return int(input())

def rl():
	return list(map(int, sys.stdin.readline().strip('\n').split()))

def Solve():
	n = ri()
	a = rl()
	b = rl()
	d = rl()
	tag = [0] * (n + 1)
	for x in d:
		if x and tag[x]:
			print('0')
			return
		tag[x] = 1
	tag = [0] * (n + 1)
	posa = [0] * (n + 1)
	tag = [0] * (n + 1)
	for i in range(0, n):
		posa[a[i]] = i
	ans = 1
	mod = int(1000000000.0 + 7)
	for i in range(0, n):
		if tag[i]:
			continue
		pos = i
		flag = 2
		while tag[pos] == 0:
			if d[pos] or a[pos] == b[pos]:
				flag = 1
			tag[pos] = 1
			nxt = posa[b[pos]]
			pos = nxt
		ans = ans * flag % mod
	print(ans)
T = ri()
while T:
	T -= 1
	Solve()


M = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = list(map(int, input().split()))
	fixed = [0] * (n + 1)
	for i in range(n):
		if d[i] != 0:
			fixed[a[i]] = 1
	c = [0] * (n + 1)
	for i in range(n):
		c[a[i]] = b[i]
	a = c
	vis = [0] * (n + 1)

	def dfs(i):
		vis[i] = 1
		c = i
		if a[i] == i:
			return False
		while a[i] != c:
			vis[a[i]] = 1
			if fixed[i] or fixed[a[i]]:
				return False
			i = a[i]
		return True
	ans = 1
	for i in range(1, n + 1):
		if not vis[i] and dfs(i):
			ans = ans * 2 % M
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	poh = [0] * n
	obr = 10 ** 9 + 7
	otv = 0
	dictt = dict()
	for i in range(n):
		dictt[a[i]] = b[i]
		if c[i] != 0 or a[i] == b[i]:
			poh[a[i] - 1] = 1
	while dictt:
		ahahah = 0
		gg = dictt.popitem()
		if poh[gg[0] - 1] == 1:
			ahahah = 1
		else:
			ahahah = 0
		ggb = gg[1]
		while ggb in dictt:
			if poh[ggb - 1] == 1:
				ahahah = 1
			ggb = dictt.pop(ggb)
		if ahahah == 0:
			otv += 1
	print(2 ** otv % obr)


m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = {i: 0 for i in range(1, n + 1)}
	for i in range(n):
		d[c[i]] = 1
	dd = {}
	for i in range(n):
		dd[a[i]] = i
	ans = 1
	for i in range(n):
		if c[i] != 0 or a[i] == b[i] or d[a[i]] == 1 or (d[b[i]] == 1):
			continue
		j = dd[b[i]]
		f = 2
		while j != i:
			if c[j] != 0:
				f = 1
			c[j] = 1
			j = dd[b[j]]
		ans = ans * f % m
		k = 1
	print(ans)


import sys
input = sys.stdin.readline
I = lambda : int(input())
A = lambda : [*map(int, input().split())]
mod = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	(a, b, c) = (A(), A(), A())
	g = {a[i]: [b[i], c[i]] for i in range(n)}
	(cycles, visi) = (0, [False] * (n + 1))
	for u in range(1, n + 1):
		need = True
		cycle_size = 0
		while not visi[g[u][0]]:
			if g[u][1] != 0:
				need = False
			(visi[g[u][0]], u) = (True, g[u][0])
			cycle_size += 1
		if need and cycle_size > 1:
			cycles += 1
	print(pow(2, cycles, mod))


import sys
input = sys.stdin.readline
M = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = [[-1, -1] for _ in range(n + 1)]
	for i in range(n):
		d[a[i]] = [b[i], c[i]]
	x = [0] * (n + 1)
	ans = 1
	for i in range(1, n + 1):
		if i == d[i][0]:
			continue
		elif x[d[i][0]] == 0:
			c = 0
			while x[d[i][0]] == 0:
				c += d[i][1]
				(x[d[i][0]], i) = (1, d[i][0])
			if c == 0:
				ans = ans * 2 % M
	print(ans)


import collections
mod = 10 ** 9 + 7

def ff(x):
	if par[x] == x:
		return x
	else:
		par[x] = ff(par[x])
		return par[x]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	ans = 1
	par = [i for i in range(0, n + 1)]
	vis = [0] * (n + 1)
	sz = [0] * (n + 1)
	for i in range(n):
		par[ff(a[i])] = ff(b[i])
	for i in range(n):
		vis[ff(c[i])] = 1
	for i in range(n):
		if a[i] == b[i]:
			vis[a[i]] = 1
	for i in range(1, 1 + n):
		if vis[ff(i)] == 0:
			ans = ans * 2 % mod
			vis[ff(i)] = 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	bi = list(map(int, input().split()))
	di = list(map(int, input().split()))
	visited = set([])
	arr = []
	for i in di:
		if i != 0:
			arr.append(i)
	graph = {i: 0 for i in range(1, n + 1)}
	for i in range(n):
		graph[ai[i]] = bi[i]

	def dfs(i):
		stack = [i]
		while stack:
			root = stack.pop()
			visited.add(root)
			if graph[root] not in visited:
				stack.append(graph[root])
	for i in arr:
		if i not in visited:
			dfs(i)
	ans = 1
	for i in range(1, n + 1):
		if i not in visited and graph[i] != i:
			dfs(i)
			ans = ans * 2 % (10 ** 9 + 7)
	print(ans)


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = int_arr()
	b = int_arr()
	c = int_arr()
	graph = {}
	done = set()
	ans = 1
	for i in range(n):
		graph[a[i]] = [b[i], i]
	for i in range(n):
		if a[i] in done:
			continue
		val = a[i]
		flag = 1
		while val not in done:
			done.add(val)
			if c[graph[val][1]] != 0 or val == graph[val][0]:
				flag = 0
			val = graph[val][0]
		if flag == 1:
			ans = ans % mod * 2
			ans %= mod
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	mo = 10 ** 9 + 7
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list(map(int, input().split()))
	graph = [[] for _ in range(n)]
	idx = [[] for _ in range(n + 1)]
	stack = []
	for i in range(n):
		idx[A[i]].append(i)
		idx[B[i]].append(i)
		if C[i] != 0:
			stack.append(i)
	for i in range(1, n + 1):
		(j, k) = idx[i]
		if j != k:
			graph[j].append(k)
			graph[k].append(j)
	vis = set()
	ans = 1
	for i in stack:
		if i not in vis:
			vis.add(i)
			stack = [i]
			while stack:
				curr = stack.pop()
				for nei in graph[curr]:
					if nei not in vis:
						stack.append(nei)
						vis.add(nei)
	for i in range(n):
		if i not in vis:
			vis.add(i)
			stack = [i]
			if A[i] != B[i]:
				ans *= 2
				ans %= mo
				while stack:
					curr = stack.pop()
					for nei in graph[curr]:
						if nei not in vis:
							stack.append(nei)
							vis.add(nei)
	return ans
for _ in range(int(input())):
	print(solve())


class dsu:

	def __init__(self, n):
		self.comp = n
		self.id = list(range(n))
		self.sz = [1] * n

	def find(s, p):
		rt = p
		while rt != s.id[rt]:
			rt = s.id[rt]
		while p != rt:
			(s.id[p], p) = (rt, s.id[p])
		return rt

	def join(s, a, b):
		if not s.connected(a, b):
			(r1, r2) = (s.find(b), s.find(a))
			s.id[r1] = s.id[r2]
			s.sz[r2] += s.sz[r1]
			s.comp -= 1
	connected = lambda this, a, b: this.find(a) == this.find(b)
	size = lambda s: s.comp
	compSize = lambda s, x: s.sz[s.find(x)]
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
O = sys.stdout.write
m = int(1000000000.0) + 7
for _ in range(*I()):
	n = I()[0]
	(a, b, c) = (I(), I(), I())
	d = dsu(n)
	(grp1, grp2) = (set(), set())
	for i in range(n):
		d.join(a[i] - 1, b[i] - 1)
	for i in range(n):
		if a[i] != b[i] and c[i]:
			grp1.add(d.find(c[i] - 1))
		if d.compSize(i) > 1:
			grp2.add(d.find(i))
	O(str(pow(2, len(grp2) - len(grp1), m)))
	O('\n')