When he's not training for IOI, Little Alawn enjoys playing with puzzles of various types to stimulate his brain. Today, he's playing with a puzzle that consists of a $2 \times n$ grid where each row is a permutation of the numbers $1,2,3,\ldots,n$.

The goal of Little Alawn's puzzle is to make sure no numbers on the same column or row are the same (we'll call this state of the puzzle as solved), and to achieve this he is able to swap the numbers in any column. However, after solving the puzzle many times, Little Alawn got bored and began wondering about the number of possible solved configurations of the puzzle he could achieve from an initial solved configuration only by swapping numbers in a column.

Unfortunately, Little Alawn got stuck while trying to solve this harder problem, so he was wondering if you could help him with it. Find the answer modulo $10^9+7$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 4 \cdot 10^5$).

The next two lines of each test case describe the initial state of the puzzle grid. Each line will be a permutation of the numbers $1,2,3,\ldots,n$ and the numbers in each column and row will be pairwise distinct.

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


-----Output-----

For each test case output a single integer, the number of possible solved configurations of the puzzle Little Alawn can achieve from an initial solved configuration only by swapping numbers in a column. As the answer can be very large, please output it modulo $10^9+7$.

The answer for each test case should be on a separate line.


-----Examples-----

Input
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
Output
2
8


-----Note-----

The two possible puzzle configurations for example $1$ are:

$[1,4,2,3]$ in the first row and $[3,2,1,4]$ in the second;

$[3,2,1,4]$ in the first row and $[1,4,2,3]$ in the second.

Source: codeforces | Difficulty: EASY
Tags: Graph algorithms

Combinatorics

Dynamic programming

Mathematics

Spanning trees


Solutions:
from collections import defaultdict
for __ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	graph = {}
	for i in range(n):
		graph[a[i]] = b[i]
	visited = defaultdict(bool)

	def dfs(u):
		visited[u] = True
		v = graph[u]
		while not visited[v]:
			visited[v] = True
			v = graph[v]
	count = 0
	for i in range(1, n + 1):
		if not visited[i]:
			count += 1
			dfs(i)
	print(pow(2, count, 10 ** 9 + 7))


from collections import Counter
import string
import math
import bisect
mod = 10 ** 9 + 7
import sys
from fractions import Fraction
from types import GeneratorType
import collections, sys, threading
sys.setrecursionlimit(10 ** 9)
threading.stack_size(10 ** 8)

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))

def solve():

	def dfs(node):
		visited[node] = 1
		for i in tree[node]:
			if visited[i] == 0:
				dfs(i)
		return
	testcases = vary(1)
	for _ in range(testcases):
		n = vary(1)
		num1 = array_int()
		num2 = array_int()
		tree = [[] for i in range(n + 1)]
		visited = [0] * (n + 1)
		for i in range(n):
			tree[num1[i]].append(num2[i])
		pairs = 0
		for i in range(1, n + 1):
			if visited[i] == 0:
				dfs(i)
				pairs += 1
		print(pow(2, pairs, 10 ** 9 + 7))
threading.Thread(target=solve).start()


from sys import stdin, stderr

def rl():
	return [int(w) for w in stdin.readline().split()]
(t,) = rl()
for _ in range(t):
	(n,) = rl()
	p1 = rl()
	p2 = rl()
	p = [0] * n
	for (x, y) in zip(p1, p2):
		p[x - 1] = y - 1
	r = 1
	for i in range(n):
		if p[i] == i:
			continue
		j = p[i]
		while j != i:
			nj = p[j]
			p[j] = j
			j = nj
		r = r * 2 % 1000000007
	print(r)


from math import *
from collections import *
from functools import *
from bisect import *
from itertools import *
from heapq import *
inf = float('inf')
ninf = -float('inf')
ip = input
alphal = 'abcdefghijklmnopqrstuvwxyz'
alphau = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
mod = 10 ** 9 + 7

def ipl():
	return list(map(int, ip().split()))

def ipn():
	return int(ip())

def ipf():
	return float(ip())

def solve():
	n = ipn()
	(a, b) = (ipl(), ipl())
	g = [-1 for _ in range(n + 1)]
	for i in range(n):
		g[a[i]] = b[i]
	v = [False] * (n + 1)
	r = 0
	for i in range(1, n + 1):
		if v[i]:
			continue
		r += 1
		j = i
		while not v[j]:
			v[j] = True
			j = g[j]
	res = 1
	for i in range(r):
		res = res * 2 % mod
	print(res)
t = ipn()
for _ in range(t):
	solve()


import sys

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

def get_array():
	return list(get_ints())

def input():
	return sys.stdin.readline().strip()

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

class DisjointSetUnion:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)
mod = 10 ** 9 + 7
T = int(input())
while T > 0:
	n = int(input())
	Arr1 = get_array()
	Arr2 = get_array()
	myset = set()
	dsu = DisjointSetUnion(n + 1)
	for i in range(n):
		a = Arr1[i]
		b = Arr2[i]
		a = dsu.find(a)
		b = dsu.find(b)
		dsu.union(a, b)
	ans = pow(2, dsu.num_sets - 1, mod)
	print(ans)
	T -= 1


from collections import defaultdict
import sys
sys.setrecursionlimit(int(1000000000.0))

def dfs(adj, root, visited):
	stack = [root]
	while len(stack):
		root = stack.pop()
		visited[root] = True
		for i in adj[root]:
			if visited[i] == False:
				stack.append(i)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	adj = defaultdict(list)
	for (i, j) in zip(a, b):
		adj[i - 1].append(j - 1)
	visited = [False] * n
	components = 0
	for i in range(n):
		if visited[i] == False:
			dfs(adj, i, visited)
			components += 1
	print(pow(2, components, int(1000000000.0 + 7)))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = [0] * n
	for i in range(n):
		p[b[i] - 1] = i
	c = [1] * n
	d = 1
	for i in range(n):
		if c[i]:
			d *= 2
			d %= 1000000007
			e = a[i]
			c[i] = 0
			while c[p[e - 1]]:
				c[p[e - 1]] = 0
				e = a[p[e - 1]]
	print(d)


from collections import Counter, defaultdict, deque
import math
from heapq import *
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	look = dict()
	for i in range(n):
		look[a[i]] = i
	unseen = set((x for x in range(n)))
	p = 0
	c = 0
	while p < n:
		if p not in unseen:
			p += 1
			continue
		start = a[p]
		cur = b[p]
		unseen.remove(p)
		while start != cur:
			unseen.remove(look[cur])
			cur = b[look[cur]]
		c += 1
	print(pow(2, c, MOD))
tt = int(input())
for test in range(tt):
	solve()


import math
mod = 10 ** 9
mod += 7
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	crr = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		crr[arr[i - 1]] = brr[i - 1]
	cnt = [0 for i in range(n + 1)]
	ans = 0
	dic = {}
	for i in range(1, n + 1):
		if not dic.get(i):
			ans += 1
			dic[i] = 1
			dic[crr[i]] = 1
			ones = 2
			twos = 0
			last = crr[i]
			while ones != twos:
				a1 = last
				b1 = crr[last]
				if dic.get(a1):
					dic[a1] += 1
					twos += 1
				else:
					dic[a1] = 1
					ones += 1
				if dic.get(b1):
					dic[b1] += 1
					twos += 1
				else:
					dic[b1] = 1
					ones += 1
				last = b1
	print(pow(2, ans, mod))


def readline():
	return map(int, input().split())
MOD = 10 ** 9 + 7

def solve():
	n = int(input())
	f = readline()
	s = readline()
	d = dict(zip(f, s))
	cnt = 0
	while d:
		cnt += 1
		(k, v) = d.popitem()
		while v != k:
			v = d.pop(v)
	print(pow(2, cnt, MOD))

def main():
	t = int(input())
	for __ in range(t):
		solve()
main()


import sys
from collections import deque
MOD = 1000000007

def inp():
	return sys.stdin.readline().strip()

def ii():
	return int(inp())

def iis():
	return [int(i) for i in inp().split()]

def solve():
	n = ii()
	(row1, row2) = (iis(), iis())
	(row1Idx, row2Idx) = ({}, {})
	for i in range(n):
		row1Idx[row1[i]] = row2Idx[row2[i]] = i
	numDS = 0
	seen = {}
	for i in range(n):
		if row1[i] in seen:
			continue
		seen[row1[i]] = True
		queue = deque()
		queue.append(row2[i])
		while queue:
			curr = queue.popleft()
			if curr in seen:
				continue
			seen[curr] = True
			queue.append(row2[row1Idx[curr]])
		numDS += 1
	return pow(2, numDS, MOD)
t = ii()
for _ in range(t):
	print(solve())


from collections import defaultdict

def pow(a, n, m):
	if n == 0:
		return 1
	x = pow(a, n // 2, m)
	if n % 2 == 0:
		return x * x % m
	else:
		return x * x * a % m

def dfs(u, g, vis):
	st = [u]
	vis[u] = 1
	while st:
		p = st.pop()
		vis[p] = 1
		for to in g[p]:
			if not vis[to]:
				st.append(to)
m = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	g = defaultdict(list)
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		a[i] -= 1
	for i in range(n):
		b[i] -= 1
		g[a[i]].append(b[i])
		g[b[i]].append(a[i])
	vis = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		if not vis[i]:
			ans += 1
			dfs(i, g, vis)
	print(pow(2, ans, m))


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	s = list(map(int, input().split()))
	r = [0] * n
	for i in range(n):
		r[f[i] - 1] = i
	ans = 1
	d = [0] * n
	for i in range(n):
		if d[i] == 1:
			continue
		ans = ans * 2 % mod
		j = i
		while d[r[s[j] - 1]] == 0:
			d[r[s[j] - 1]] = 1
			j = r[s[j] - 1]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l = []
	d = {}
	for j in range(n):
		l.append(0)
		l1[j] -= 1
		l2[j] -= 1
		d[l1[j]] = l2[j]
	c = 0
	for j in range(n):
		if l[l1[j]] == 0:
			c += 1
			a = l1[j]
			while l[a] == 0:
				l[a] = 1
				a = d[a]
	print(2 ** c % (10 ** 9 + 7))


from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	seen = defaultdict(lambda : False)
	a = []
	for j in range(2):
		b = list(map(int, input().split()))
		a.append(b)
	ind = defaultdict(lambda : -1)
	for j in range(n):
		ind[a[1][j]] = j
	ans = 0
	for j in range(n):
		if not seen[a[0][j]]:
			ans += 1
			pos = ind[a[0][j]]
			next = a[0][j]
			while not seen[next]:
				seen[next] = True
				pos = ind[next]
				next = a[0][pos]
	mod = 10 ** 9 + 7
	print(2 ** ans % mod)


import sys
import math
import heapq

def input():
	return sys.stdin.readline().strip('\n')

def I():
	return input()

def II():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def isPerfectSquare(x):
	return int(math.sqrt(x)) ** 2 == x
sys.setrecursionlimit(500000)
from collections import OrderedDict
MOD = 10 ** 9 + 7
for _ in range(II()):
	graph = {}

	def dfs(x):
		if not visited[x]:
			visited[x] = 1
			dfs(graph[x])
	n = II()
	a = LI()
	b = LI()
	visited = [0] * (n + 1)
	for i in range(n):
		graph[a[i]] = b[i]
	ans = 1
	for i in range(n):
		if visited[a[i]] == 0:
			nxt = a[i]
			while visited[nxt] == 0:
				visited[nxt] = 1
				nxt = graph[nxt]
			ans = ans * 2 % MOD
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	graph = {}
	for i in range(n):
		graph[arr1[i]] = i
	seen = set()
	count = 0
	for i in range(n):
		if i not in seen:
			count += 1
			while i not in seen:
				seen.add(i)
				(arr1[i], arr2[i]) = (arr2[i], arr1[i])
				i = graph[arr1[i]]
	ans = 2 ** count % (10 ** 9 + 7)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = list(map(int, input().split()))
	d1 = {}
	d2 = {}
	for i in range(n):
		d1[arr[i]] = arr1[i]
	vis = {}
	count = 0
	mod = 10 ** 9 + 7
	for i in arr1:
		if i not in vis:
			j = d1[i]
			vis[i] = True
			while j not in vis:
				vis[j] = True
				j = d1[j]
			count += 1
	print(pow(2, count, 10 ** 9 + 7))


for t in range(int(input())):
	n = int(input())
	a = [int(s) for s in input().split()]
	b = [int(s) for s in input().split()]
	c = [-1 for i in range(n)]
	for i in range(n):
		c[a[i] - 1] = b[i] - 1
	count_loops = 0
	for i in range(n):
		if c[i] < 0:
			continue
		count_loops += 1
		j = i
		while True:
			k = c[j]
			c[j] = -1
			j = k
			if i == j:
				break
	res = 1
	x = 10 ** 9 + 7
	for i in range(count_loops):
		res *= 2
		res %= x
	print(res)


p = 10 ** 9 + 7

def power(x, y, p):
	b = bin(y)[2:]
	start = x
	answer = 1
	for i in range(len(b) - 1, -1, -1):
		if b[i] == '1':
			answer = answer * start % p
		start = start * start % p
	return answer

def process(M):
	n = len(M[0])
	d = {}
	S = set([])
	for i in range(n):
		a = M[0][i]
		b = M[1][i]
		if a != b:
			d[a] = b
			S.add(a)
			S.add(b)
	counting = 0
	while len(S) > 0:
		to_remove = set([])
		for x in S:
			break
		to_remove.add(x)
		while d[x] not in to_remove:
			to_remove.add(d[x])
			x = d[x]
		for x in to_remove:
			S.remove(x)
		counting += 1
	return power(2, counting, p)
t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	print(process([A, B]))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = [None] * (n + 1)
	for i in range(n):
		p[a[i]] = i
	c = 0
	w = [False] * (n + 1)
	for i in range(1, n + 1):
		if not w[i]:
			c += 1
			q = [i]
			qi = 0
			while qi < len(q):
				x = q[qi]
				qi += 1
				v = b[p[x]]
				if not w[v]:
					w[v] = True
					q.append(v)
	print(pow(2, c, int(1000000000.0 + 7)))
for i in range(int(input())):
	solve()


def calc():
	n = int(input())
	p = list(map(int, input().split(' ')))
	q = list(map(int, input().split(' ')))
	parent = [-1] * (n + 1)
	pinx = [-1] * (n + 1)
	qinx = [-1] * (n + 1)
	for i in range(n):
		pinx[p[i]] = i
		qinx[q[i]] = i
	k = -1
	for i in range(n):
		if p[i] == q[i]:
			print(0)
			return
		x = p[i]
		if parent[x] == -1:
			k += 1
		while parent[x] == -1:
			parent[x] = k
			inx = pinx[x]
			x = q[inx]
	print(2 ** (k + 1) % 1000000007)
t = int(input())
for _i in range(t):
	calc()


def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	combined = zip(A, B)
	combined = sorted(combined, key=lambda x: x[0])
	B_perm = [x[1] for x in combined]
	node___color = [-1 for x in B_perm]
	color = 0
	cycles = []
	for start_node in range(n):
		if node___color[start_node] != -1:
			continue
		node___color[start_node] = color
		curr_node = start_node
		cycle_size = 1
		while True:
			next_node = B_perm[curr_node] - 1
			if next_node == start_node:
				break
			node___color[next_node] = color
			cycle_size += 1
			curr_node = next_node
		cycles.append((cycle_size, color))
		color += 1
	print(pow(2, len(cycles), 10 ** 9 + 7))
t = int(input())
for _ in range(t):
	solve()


for t in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split(' ')))
	arr2 = list(map(int, input().split(' ')))
	arr = [[0, 0] for i in range(n)]
	for i in range(n):
		arr[arr1[i] - 1][0] = arr2[i]
	point = 0
	k = -1
	for i in range(n):
		k += 1
		m = 0
		while arr[k][1] == 0:
			arr[k][1] = 1
			k = arr[k][0] - 1
			m += 1
		if m > 0:
			point += 1
	print(2 ** point % 1000000007)


import sys, threading

def main():
	from collections import defaultdict
	t = int(input())
	for _ in range(t):
		n = int(input())
		first = list(map(int, input().split()))
		second = list(map(int, input().split()))
		graph = defaultdict(list)
		for idx in range(n):
			(num1, num2) = (first[idx], second[idx])
			graph[num1].append(num2)
		seen = [False for _ in range(n)]

		def dfs(start):
			seen[start - 1] = True
			for other in graph[start]:
				if not seen[other - 1]:
					dfs(other)
		ans = 0
		for node in range(1, n + 1):
			if not seen[node - 1]:
				ans += 1
				dfs(node)
		print(2 ** ans % (10 ** 9 + 7))
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


from sys import stdin, stdout
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	A = list(map(int, stdin.readline().split()))
	B = list(map(int, stdin.readline().split()))
	C = []
	visited = [False for i in range(n)]
	c = 0
	for i in range(n):
		C.append((A[i], B[i]))
	C = sorted(C, key=lambda x: x[0])
	for i in range(n):
		if not visited[i]:
			x = i + 1
			visited[i] = True
			while C[i][1] != x:
				i = C[i][1] - 1
				visited[i] = True
			c += 1
	print(2 ** c % (10 ** 9 + 7))


def sol(A, B):
	dic = {}
	for (a, b) in zip(A, B):
		dic[a] = b
	visited = [False for _ in range(len(A) + 1)]
	count = 0
	for a in A:
		if not visited[a]:
			i = a
			visited[i] = True
			while not visited[dic[i]]:
				visited[dic[i]] = True
				i = dic[i]
			count += 1
	return 2 ** count % 1000000007
x = int(input())
for _ in range(x):
	y = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(sol(A, B))


def l_a_p(n, row1, row2):
	used = [False] * n
	row2_number_to_id = {}
	for (i, x) in enumerate(row2):
		row2_number_to_id[x] = i
	cycles = 0
	i = 0
	while i < n:
		if not used[i]:
			k = i
			used[k] = True
			last = row2[k]
			next = -1
			while last != next:
				curr = row1[k]
				k = row2_number_to_id[curr]
				used[k] = True
				next = row1[k]
			cycles += 1
		i += 1
	return int(pow(2, cycles, int(1000000000.0 + 7)))

def solve():
	t = int(input())
	for _ in range(t):
		n = int(input())
		row1 = [int(x) for x in input().split()]
		row2 = [int(x) for x in input().split()]
		print(l_a_p(n, row1, row2))
solve()


class Union:

	def __init__(self, n):
		self.n = n
		self.parent = [i for i in range(n + 1)]
		self.size = [1] * (n + 1)

	def find(self, x):
		if self.parent[x] == x:
			return x
		self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		if x != y:
			if self.size[x] < self.size[y]:
				(x, y) = (y, x)
			self.parent[y] = x
			self.size[x] += self.size[y]

	def count(self):
		ans = 0
		for i in range(self.n + 1):
			if self.parent[i] == i and self.size[i] > 1:
				ans += 1
		return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	obj = Union(n)
	for i in range(n):
		obj.union(obj.find(a[i]), obj.find(b[i]))
	print(pow(2, obj.count(), 1000000007))


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	adj = [0] * n
	vis = [0] * n
	for i in range(n):
		adj[a[i] - 1] = b[i] - 1
	res = 1
	for i in range(n):
		if vis[i] == 0:
			v = i
			vis[v] = 1
			while vis[adj[v]] == 0:
				v = adj[v]
				vis[v] = 1
			res = res * 2 % MOD
	print(res)


import math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
one = lambda : int(I())
more = lambda : map(int, I().split())
linput = lambda : list(more())
mod = 10 ** 9 + 7
inf = 10 ** 18 + 1

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	return (a + b - 1) // b
for _ in range(one()):
	n = one()
	a = linput()
	b = linput()
	g = [[] for i in range(n + 1)]
	for i in range(n):
		g[a[i]].append(b[i])
		g[b[i]].append(a[i])
	ans = 1
	st = []
	vis = [0] * (n + 1)
	for i in range(1, n + 1):
		temp = 0
		if vis[i] == 0:
			st.append(i)
			vis[i] = 1
			while st:
				k = st.pop(0)
				temp += 1
				for j in g[k]:
					if vis[j] == 0:
						vis[j] = 1
						st.append(j)
		ans *= pow(2, temp > 0, mod)
		ans %= mod
	print(ans)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def fi():
	return float(input())

def si():
	return input()

def msi():
	return map(str, input().split())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def lsi():
	return list(msi())

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	return x * y // gcd(x, y)
mod = 1000000007

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def ceil2(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def modu(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return -999999999
	else:
		return inv * a % m
from math import log, factorial, cos, tan, sin, radians, floor, sqrt, ceil, log2
import bisect
import random
import string
from decimal import *
getcontext().prec = 50
abc = 'abcdefghijklmnopqrstuvwxyz'
pi = 3.141592653589793

def gcd1(a):
	if len(a) == 1:
		return a[0]
	ans = a[0]
	for i in range(1, len(a)):
		ans = gcd(ans, a[i])
	return ans

def mykey(x):
	return len(x)

def checkper_sq(n):

	def check(n, mod):
		for i in range(mod):
			if i * i % mod == n % mod:
				return True
		return False
	for i in range(3, 101):
		if not check(n, i):
			return False
	return True

def main():
	for _ in range(ii()):
		n = ii()
		l = []
		for i in range(2):
			c = li()
			l.append(c)
		f = [0] * (n + 5)
		vis = [0] * (n + 5)
		for i in range(n):
			f[l[0][i]] = l[1][i]
		p = 0
		for i in range(1, n + 1):
			if vis[i] == 0:
				vis[i] = 1
				cur = f[i]
				while vis[cur] == 0:
					vis[cur] = 1
					cur = f[cur]
				p += 1
		print(pow(2, p, mod))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def main():
	n_mod = 10 ** 9 + 7
	t = int(input())
	for _ in range(t):
		n_comp = 0
		n = int(input())
		source = [int(x) - 1 for x in input().split()]
		graph = [0 for _ in range(n)]
		i = 0
		for x in map(int, input().split()):
			graph[source[i]] = int(x) - 1
			i += 1
		for i in range(n):
			if graph[i] != -1:
				n_comp += 1
				next_node = graph[graph[i]]
				while next_node != -1:
					old_node = next_node
					next_node = graph[next_node]
					graph[old_node] = -1
		print(2 ** n_comp % n_mod)
main()


mod = 7 + 10 ** 9
for _ in range(int(input())):
	sfd = input()
	l1 = [int(i) for i in input().split()]
	l2 = [int(i) for i in input().split()]
	vis = [0] * len(l1)
	d1 = dict()
	d2 = dict()
	ct = 0
	ans = 0
	for i in range(len(l1)):
		d1[l1[i]] = i
	for i in range(len(l2)):
		d2[l2[i]] = i
	for i in range(len(l1)):
		if vis[i] == 0:
			st = l1[i]
			c = st
			part = l2[i]
			ct = 0
			vis[i] = 1
			while part != st:
				c = part
				if ct % 2 == 0:
					part = l1[d1[c]]
					vis[d1[c]] = 1
				else:
					part = l2[d1[c]]
				ct += 1
			ans = (ans + 1) % mod
	print(2 ** ans % mod)


def pow_h(base, degree, module):
	ans = 1
	while degree > 0:
		if degree % 2 == 1:
			ans *= base
			ans = ans % module
		base = base ** 2
		base = base % module
		degree //= 2
	return ans
t = int(input())
for k in range(t):
	n = int(input())
	a = [list(map(int, input().split())), list(map(int, input().split())), list(map(lambda p: 0, list(range(n))))]
	place = list(range(n + 1))
	for i in range(n):
		place[a[0][i]] = i
	cnt = 0
	for i in range(n):
		if a[2][i] == 0:
			cnt += 1
			a[2][i] = 1
			j = a[1][i]
			while place[j] != i:
				a[2][place[j]] = i + 1000000
				j = a[1][place[j]]
	print(pow_h(2, cnt, 1000000007))


def f(a, b):
	n = len(a)
	A = [0] * (n + 1)
	for i in range(n):
		A[a[i]] = b[i]
	vis = [0] * (n + 1)
	cnt = 0
	for pos in range(1, n + 1):
		if vis[pos] == 0:
			cnt += 1
			vis[pos] = 1
			q = [pos]
			while q:
				cr = q.pop(0)
				if vis[A[cr]] == 0:
					q.append(A[cr])
					vis[A[cr]] = 1
	return pow(2, cnt, 10 ** 9 + 7)
for _ in range(int(input())):
	l = input()
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	print(f(a, b))


from sys import stdin, stdout
input = stdin.readline

def output(answer):
	stdout.write('{}\n'.format(answer))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_components(graph, n):
	visited = [0 for i in range(n)]
	count = 0
	for i in range(n):
		if visited[i] == 1:
			continue
		stack = [i]
		visited[i] = 1
		count += 1
		while stack:
			node = stack.pop()
			for e in graph[node]:
				if visited[e] == 0:
					visited[e] = 1
					stack.append(e)
	return count
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	da = [None for i in range(n + 1)]
	db = [None for i in range(n + 1)]
	for (index, value) in enumerate(a):
		da[value] = index
	for (index, value) in enumerate(b):
		db[value] = index
	graph = [[] for i in range(n)]
	for index in range(n):
		(va, vb) = (a[index], b[index])
		graph[index].append(db[va])
		graph[index].append(da[vb])
	p = number_of_components(graph, n)
	mod = int(1000000000.0 + 7)
	print(power(2, p, mod))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
N = 1000000007

def p(n):
	a = 1
	for _ in range(n):
		a = a * 2 % N
	return a
t = inp()
for _ in range(t):
	n = inp()
	a = [inlt(), inlt()]
	nums = {}
	g = []
	for i in range(n):
		g.append([])
	ans = -1
	for i in range(n):
		if a[0][i] == a[1][i]:
			ans = 0
			break
		if a[0][i] in nums:
			if nums[a[0][i]] == -1:
				ans = 0
				break
			g[i].append(nums[a[0][i]])
			g[nums[a[0][i]]].append(i)
			nums[a[0][i]] = -1
		else:
			nums[a[0][i]] = i
		if a[1][i] in nums:
			if nums[a[1][i]] == -1:
				ans = 0
				break
			g[i].append(nums[a[1][i]])
			g[nums[a[1][i]]].append(i)
			nums[a[1][i]] = -1
		else:
			nums[a[1][i]] = i
	if ans == 0:
		print(0)
		continue
	visited = [False] * n
	visit_queue = []
	num_components = 0
	for i in range(n):
		if not visited[i]:
			visit_queue.append(i)
			num_components += 1
		while len(visit_queue) > 0:
			u = visit_queue.pop()
			if visited[u]:
				continue
			visited[u] = True
			for v in g[u]:
				if not visited[v]:
					visit_queue.append(v)
	print(p(num_components))


import sys
from os import path
import bisect
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output1.txt', 'w')
from heapq import heappop, heappush, heapify
from math import ceil
from collections import defaultdict
maxi = sys.maxsize
mini = -maxi
size = 4 * pow(10, 5) + 1
g = defaultdict(list)
visit = [False for i in range(size)]
modulo = 10 ** 9 + 7
dp = [1]
for i in range(1, size):
	c = dp[i - 1]
	dp.append(c * 2)
	dp[i] %= modulo

def connect(v):
	q = [v]
	visit[v] = True
	while q:
		u = q.pop(0)
		for i in g[u]:
			if not visit[i]:
				q.append(i)
				visit[i] = True
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		g[a[i] - 1].append(b[i] - 1)
		g[b[i] - 1].append(a[i] - 1)
	d = 0
	for i in range(n):
		if not visit[i]:
			d += 1
			connect(i)
	g.clear()
	for i in range(n):
		visit[i] = False
	print(dp[d])


R = input
I = lambda : [*map(int, R().split())]
for _ in '*' * int(R()):
	n = int(R())
	q = {}
	(a, b) = (I(), I())
	for i in range(n):
		q[a[i]] = b[i]
	t = 0
	for i in a:
		j = i
		if b[i - 1] != 0:
			t += 1
			while q[j] != i:
				b[j - 1] = 0
				j = q[j]
			b[j - 1] = 0
	print(pow(2, t, 10 ** 9 + 7))


t = int(input())
for test in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr1_idx = {}
	arr2_idx = {}
	for (idx, val) in enumerate(arr1):
		arr1_idx[val] = idx
	for (idx, val) in enumerate(arr2):
		arr2_idx[val] = idx
	visited = [False for i in range(n)]
	count = 0
	for i in range(n):
		if visited[i]:
			continue
		visited[i] = True
		source = arr1[i]
		dest = arr2[i]
		idx = arr1_idx.get(dest)
		visited[idx] = True
		while source != arr2[idx]:
			dest = arr2[idx]
			idx = arr1_idx.get(dest)
			visited[idx] = True
		count += 1
	print(2 ** count % (10 ** 9 + 7))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ai = {}
	bi = {}
	k = 0
	for i in range(n):
		ai[a[i]] = i
		bi[b[i]] = i
	for i in a:
		if ai[i] != -1:
			j = b[ai[i]]
			ai[i] = -1
			while i != j:
				p = j
				j = b[ai[j]]
				ai[p] = -1
			k += 1
	print(2 ** k % 1000000007)


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
mx = 10 ** 9 + 7

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for _ in range(inp()):
	n = inp()
	l1 = inlt()
	l2 = inlt()
	d = []
	for i in range(n):
		d.append([l1[i], l2[i]])
	d.sort()
	visited = [0 for i in range(n)]
	cnt = 0
	seen = set()
	strt = 1
	temp = 0
	while len(seen) != n:
		if visited[strt - 1]:
			strt += 1
			if temp:
				cnt += 1
				temp = 0
		else:
			visited[strt - 1] = 1
			seen.add(d[strt - 1][0])
			strt = d[strt - 1][1]
			temp += 1
	print(powerMod(2, cnt + 1, mx))


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def primeNums():
	N = 10 ** 5
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
for _ in range(getInt()):
	n = getInt()
	arr1 = zzz()
	arr2 = zzz()
	ind1 = [0] * n
	ind2 = [0] * n
	for i in range(n):
		ind1[arr1[i] - 1] = i
		ind2[arr2[i] - 1] = i
	vis = [0] * n
	group = 0
	for i in range(n):
		if vis[i]:
			continue
		group += 1
		que = deque()
		que.append(i)
		vis[i] = 1
		while que:
			x = que.pop()
			nei = [arr1[x] - 1, arr2[x] - 1]
			for i in nei:
				nx = [ind1[i], ind2[i]]
				for j in nx:
					if vis[j]:
						continue
					que.append(j)
					vis[j] = 1
	ans = 1
	for i in range(1, group + 1):
		ans *= 2
		ans %= mod
	print(ans)


import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())
M = 10 ** 9 + 7
O = []

def inv(p):
	n = len(p)
	q = [0] * n
	for i in range(n):
		q[p[i] - 1] = i
	return q
for _ in range(int(Z())):
	n = int(Z())
	a = list(Y())
	b = list(Y())
	ia = inv(a)
	t = 0
	c = [1] * n
	for i in range(n):
		if c[i]:
			s = 0
			j = i
			v = -1
			while v != a[i]:
				j = ia[b[j] - 1]
				s += 1
				v = a[j]
				c[j] = 0
			if s > 1:
				t += 1
	O.append(str(pow(2, t, M)))
print('\n'.join(O))


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
MOD = 1000000007

def solve(N, A, B):
	T = [-1] * N
	for i in range(N):
		T[A[i] - 1] = B[i] - 1
	seen = [False] * N
	n = 0
	for i in range(N):
		if seen[i]:
			continue
		j = i
		while not seen[j]:
			seen[j] = True
			j = T[j]
		n += 1
	return pow(2, n, MOD)
T0 = int(input())
for _ in range(T0):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(solve(N, A, B))


import math
import os
import sys
from sys import *
from decimal import *
from io import BytesIO, IOBase
from itertools import accumulate, combinations, permutations, combinations_with_replacement, product
from collections import *
M = 10 ** 9 + 7
import heapq
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchcount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] == key:
			return mid
		if arr[mid] <= key:
			left = mid + 1
		else:
			right = mid - 1
	return -1

def ternarysearch(arr, n, key):
	(l, r) = (0, n - 1)
	while l <= r:
		mid = (-l + r) // 3 + l
		mid2 = mid + (-l + r) // 3
		if arr[mid] == key:
			return mid
		if arr[mid2] == key:
			return mid2
		if arr[mid] > key:
			r = mid - 1
		elif arr[mid2] < key:
			l = mid2 + 1
		else:
			l = mid + 1
			r = mid2 - 1
	return -1

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, M):
	if b == 1:
		return a % M
	if b == 0:
		return 1
	if b % 2 == 0:
		ans = binpowmodulus(a, b // 2, M)
		return ans * ans % M
	else:
		ans = binpowmodulus(a, (b - 1) // 2, M)
		return ans * a % M * ans % M

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynum(x, l, r, a):
	if x >= l and x <= r:
		a.append(x)
	if x > r:
		a.append(x)
		return a
	if x < 10000000000.0:
		luckynum(x * 10 + 4, l, r, a)
		luckynum(x * 10 + 7, l, r, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a

def interact(type, x):
	if type == 'r':
		inp = input()
		return inp.strip()
	else:
		print(x, flush=True)

def findTrailingZeros(n):
	count = 0
	while n >= 5:
		n //= 5
		count += n
	return count

def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1
res = set()

def solven(p, l, a, b, n):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solven(p * 10 + a, l + 1, a, b, n)
	solven(p * 10 + b, l + 1, a, b, n)

def subsetsUtil(A, subset, index, d):
	print(*subset)
	s = sum(subset)
	d.append(s)
	for i in range(index, len(A)):
		subset.append(A[i])
		subsetsUtil(A, subset, i + 1, d)
		subset.pop(-1)
	return d

def subsetSums(arr, l, r, d, sum=0):
	if l > r:
		d.append(sum)
		return
	subsetSums(arr, l + 1, r, d, sum + arr[l])
	subsetSums(arr, l + 1, r, d, sum)
	return d

def print_factors(x):
	factors = []
	for i in range(1, x + 1):
		if x % i == 0:
			factors.append(i)
	return factors

def calc(X, d, ans, D):
	if len(X) == 0:
		return
	i = X.index(max(X))
	ans[D[max(X)]] = d
	Y = X[:i]
	Z = X[i + 1:]
	calc(Y, d + 1, ans, D)
	calc(Z, d + 1, ans, D)

def good(b):
	l = []
	i = 0
	while len(b) != 0:
		if b[i] < b[len(b) - 1 - i]:
			l.append(b[i])
			b.remove(b[i])
		else:
			l.append(b[len(b) - 1 - i])
			b.remove(b[len(b) - 1 - i])
	if l == sorted(l):
		return True
	return False

def generate(st, s):
	if len(s) == 0:
		return
	if s not in st:
		st.add(s)
		for i in range(len(s)):
			t = list(s).copy()
			t.remove(s[i])
			t = ''.join(t)
			generate(st, t)
	return

def largestincreasingsubsequence(A):
	l = [1] * len(A)
	sub = []
	for i in range(1, len(l)):
		for k in range(i):
			if A[k] < A[i]:
				sub.append(l[k])
		l[i] = 1 + max(sub, default=0)
	return max(l, default=0)

def findOR(nums, N):
	prefix_sum = 0
	result = 0
	for i in range(N):
		result |= nums[i]
		prefix_sum += nums[i]
		result |= prefix_sum
	return result

def OR(a, n):
	ans = a[0]
	for i in range(1, n):
		ans |= a[i]
	return ans

def toString(List):
	return ''.join(List)

def permute(a, l, r, p):
	if l == r:
		p.append(toString(a))
	else:
		for i in range(l, r + 1):
			(a[l], a[i]) = (a[i], a[l])
			permute(a, l + 1, r, p)
			(a[l], a[i]) = (a[i], a[l])

def squareRoot(number, precision):
	start = 0
	(end, ans) = (number, 1)
	while start <= end:
		mid = int((start + end) / 2)
		if mid * mid == number:
			ans = mid
			break
		if mid * mid < number:
			start = mid + 1
		else:
			end = mid - 1
	increment = 0.1
	for i in range(0, precision):
		while ans * ans <= number:
			ans += increment
		ans = ans - increment
		increment = increment / 10
	return ans

def countRectangles(l, w):
	squareSide = math.gcd(l, w)
	return int(l * w / (squareSide * squareSide))

def count_same_digit(L, R):
	tmp = 0
	ans = 0
	n = int(math.log10(R) + 1)
	for i in range(0, n):
		tmp = tmp * 10 + 1
		for j in range(1, 10):
			if L <= tmp * j and tmp * j <= R:
				ans += 1
	return ans

def findCrossOver(arr, low, high, x):
	if arr[high] <= x:
		return high
	if arr[low] > x:
		return low
	mid = (low + high) // 2
	if arr[mid] <= x and arr[mid + 1] > x:
		return mid
	if arr[mid] < x:
		return findCrossOver(arr, mid + 1, high, x)
	return findCrossOver(arr, low, mid - 1, x)

def Kclosest(arr, x, k, n, ans):
	l = findCrossOver(arr, 0, n - 1, x)
	r = l + 1
	count = 0
	if arr[l] == x:
		l -= 1
	while l >= 0 and r < n and (count < k):
		if x - arr[l] < arr[r] - x:
			ans.append(arr[l])
			l -= 1
		else:
			ans.append(arr[r])
			r += 1
		count += 1
	while count < k and l >= 0:
		ans.append(arr[l])
		l -= 1
		count += 1
	while count < k and r < n:
		ans.append(arr[r])
		r += 1
		count += 1
	return ans

def calcSum(arr, n, k):
	l = []
	sum = 0
	for i in range(k):
		sum += arr[i]
	l.append(sum)
	for i in range(k, n):
		sum = sum - arr[i - k] + arr[i]
		l.append(sum)
	return l
import math
MAX = 10 ** 5
prefix = [0] * (MAX + 1)

def buildPrefix():
	prime = [1] * (MAX + 1)
	p = 2
	while p * p <= MAX:
		if prime[p] == 1:
			i = p * 2
			while i <= MAX:
				prime[i] = 0
				i += p
		p += 1
	for p in range(2, MAX + 1):
		prefix[p] = prefix[p - 1]
		if prime[p] == 1:
			prefix[p] += 1

def query(L, R):
	return prefix[R] - prefix[L - 1]

def maxSubArraySum(a, size):
	max_so_far = a[0]
	curr_max = a[0]
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far

def solve(n, k):
	if n == 1 and k == 1:
		return 0
	mid = 2 ** (n - 1) // 2
	if k <= mid:
		return solve(n - 1, k)
	else:
		return solve(n - 1, k - mid) == 0

def solvr(s, p):
	if len(s) == 0:
		print(p, end=' ')
		return
	op1 = p
	op2 = p + s[0]
	s = s[1:]
	solvr(s, op1)
	solvr(s, op2)
	return

def paranthesis(n, m, ans, l):
	if n == 0 and m == 0:
		print(ans)
		return
	if n != 0:
		op1 = ans + '('
		paranthesis(n - 1, m, op1, l)
	if m > n:
		op2 = ans + ')'
		paranthesis(n, m - 1, op2, l)

def lcs(s, r):
	rr = len(r)
	ss = len(s)
	l = [[0] * (rr + 1) for i in range(ss + 1)]
	for i in range(1, ss + 1):
		for j in range(1, rr + 1):
			if s[i - 1] == r[j - 1]:
				l[i][j] = l[i - 1][j - 1] + 1
			else:
				l[i][j] = max(l[i - 1][j], l[i][j - 1])
	return l[ss][rr]

class Graph(object):

	def __init__(self, vertices):
		self.graph = defaultdict(list)
		self.V = vertices

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def connectedComponents(self):
		unvisited = set(range(self.V))
		queue = deque()
		count = 0
		while len(unvisited) > 0:
			count += 1
			v = next(iter(unvisited))
			unvisited.remove(v)
			queue.append(v)
			while len(queue) > 0:
				v = queue.popleft()
				for w in self.graph[v]:
					if w in unvisited:
						unvisited.remove(w)
						queue.append(w)
		return count

def main():
	for _ in range(int(input())):
		n = int(input())
		arr1 = list(map(int, input().split()))
		arr2 = list(map(int, input().split()))
		g = Graph(n)
		for i in range(n):
			g.addEdge(arr1[i] - 1, arr2[i] - 1)
		print(2 ** g.connectedComponents() % (10 ** 9 + 7))
main()


t = int(input())
p = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	ar = [list(map(int, input().split())), list(map(int, input().split()))]
	li = [0] * (n + 1)
	di = dict(zip(ar[0], ar[1]))
	w = 1
	for i in ar[0]:
		x = di[i]
		if li[i] == 0:
			w *= 2
			if w > p:
				w = w % p
			while x != i:
				li[x] = 1
				x = di[x]
		li[i] = 1
	print(w)


def nPossibleConfigurations(puzzle):
	nConfigurations = 1
	row1_values = puzzle.copy().keys()
	for row1_value in row1_values:
		if row1_value in puzzle:
			row2_value = puzzle.pop(row1_value)
			while row2_value != row1_value:
				row2_value = puzzle.pop(row2_value)
			nConfigurations = nConfigurations * 2 % 1000000007
	return nConfigurations

def testCase_1534c():
	input()
	return {value1: value2 for (value1, value2) in zip(input().split(), input().split())}
tuple((print(nPossibleConfigurations(testCase_1534c())) for x in range(int(input()))))


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())

def solve():
	n = ii()
	arr = rr()
	brr = rr()
	hmap = {i: j for (i, j) in zip(arr, brr)}
	ok = defaultdict(lambda : 0)
	c = 0
	for i in range(1, n):
		if not ok[i]:
			c += 1
			start = i
			ok[start] = 1
			last = hmap[start]
			while last != start:
				ok[last] = 1
				last = hmap[last]
	mod = 10 ** 9
	mod += 7
	print(pow(2, c, mod))
for _ in ' ' * ii():
	solve()


import math, sys
from itertools import permutations
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
MOD = int(1000000000.0) + 7
INF = float('inf')

def solve():
	n = int(input())
	a1 = list(map(int, input().split()))
	a2 = list(map(int, input().split()))
	g = defaultdict(list)
	for i in range(n):
		g[a1[i]].append(a2[i])
	p = 0
	visited = set()
	for i in range(1, n + 1):
		if i in visited:
			continue
		p += 1
		s = [i]
		while s:
			node = s.pop()
			if node in visited:
				continue
			visited.add(node)
			for child in g[node]:
				s.append(child)
	print(pow(2, p, MOD))

def main():
	ts = 1
	ts = int(input())
	for t in range(1, ts + 1):
		solve()

def input():
	return sys.stdin.readline().rstrip('\n').strip()

def print(*args, sep=' ', end='\n'):
	first = True
	for arg in args:
		if not first:
			sys.stdout.write(sep)
		sys.stdout.write(str(arg))
		first = False
	sys.stdout.write(end)
main()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		if a[i] == b[i]:
			print(0)
			return
	cc = 0
	d = {}
	for i in range(n):
		d[a[i]] = b[i]
	marked = [False] * (n + 1)
	for x in a:
		if not marked[x]:
			cc += 1
			z = x
			while not marked[z]:
				marked[z] = True
				z = d[z]
	ans = 1
	for i in range(cc):
		ans *= 2
		ans %= 10 ** 9 + 7
	print(ans)

def main():
	for _ in range(int(input())):
		solve()
main()


from collections import Counter

def find(x):
	if par[x] == x:
		return x
	par[x] = find(par[x])
	return par[x]

def union(x, y):
	dx = find(x)
	dy = find(y)
	if dx != dy:
		if count[dx] >= count[dy]:
			(dx, dy) = (dy, dx)
		par[dx] = dy
		count[dy] += count[dx]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	count = [1 for i in range(n + 1)]
	par = [i for i in range(n + 1)]
	for i in range(n):
		union(a[i], b[i])
	for i in range(n):
		par[i] = find(par[i])
	fin_arr = Counter(par)
	ans = 0
	m = 10 ** 9 + 7
	for i in fin_arr:
		if fin_arr[i] > 1:
			ans = (ans + 1) % m
	print(pow(2, ans, m))


t = int(input())
for tc in range(1, t + 1):
	n = int(input())
	r1 = list(map(int, input().split()))
	r2 = list(map(int, input().split()))
	edges = [0] * n
	for i in range(n):
		edges[r1[i] - 1] = r2[i] - 1
	cycles = [-1] * n
	cycle = 0
	for i in range(n):
		if cycles[i] == -1:
			cycles[i] = cycle
			j = edges[i]
			while j != i:
				cycles[j] = cycle
				j = edges[j]
			cycle += 1
	sol = 1
	for i in range(cycle):
		sol = 2 * sol % 1000000007
	print(sol)


def find(node, arr):
	if arr[node] == node:
		return node
	arr[node] = find(arr[node], arr)
	return arr[node]

def union(a, b, arr):
	x = find(a, arr)
	y = find(b, arr)
	if x != y:
		arr[x] = y

def solve(a, b):
	mod = 10 ** 9 + 7
	arr = [0] * (len(a) + 1)
	for i in range(1, len(a) + 1):
		arr[i] = i
	for i in range(len(a)):
		union(a[i], b[i], arr)
	c = 0
	ans = []
	for i in range(len(a)):
		ans.append(find(a[i], arr))
	n = len(set(ans))
	ans = pow(2, n)
	return ans % mod
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(solve(a, b))


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

def main():
	for _ in range(int(input())):
		n = int(input())
		one = list(map(int, input().split()))
		two = list(map(int, input().split()))
		idx = [0] * (n + 1)
		for (i, item) in enumerate(one):
			idx[item] = i
		ans = 1
		for i in range(n):
			(x, y) = (one[i], two[i])
			if x == -1:
				continue
			one[i] = -1
			while two[idx[y]] != x:
				one[idx[y]] = -1
				y = two[idx[y]]
			one[idx[y]] = -1
			ans = (ans << 1) % mod
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
m = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	apos = dict()
	bpos = dict()
	for i in range(n):
		apos[a[i]] = i + 1
		bpos[b[i]] = i + 1
	cyc = 0
	ans = 1
	check = [-1] * (n + 1)
	for i in range(n):
		t = a[i]
		if check[t] == -1:
			while check[t] < 0:
				check[t] = cyc
				t = b[apos[t] - 1]
			cyc += 1
			ans = ans * 2 % m
	print(ans)


def num_cycles(d):
	c = 0
	seen = [0] * (n + 1)
	for i in range(1, n + 1):
		if seen[i]:
			continue
		c += 1
		p = d[i]
		seen[i] = 1
		while not seen[p]:
			seen[p] = 1
			p = d[p]
	return c
for _ in range(int(input())):
	n = int(input())
	line1 = [0] + list(map(int, input().split()))
	d = [0] * (n + 1)
	for (i, x) in enumerate(map(int, input().split()), start=1):
		d[x] = line1[i]
	ans = pow(2, num_cycles(d), 10 ** 9 + 7)
	print(ans)


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d1 = dict()
	mod = 1000000007
	for i in range(n):
		d1.setdefault(a[i], b[i])
	c = 0
	d2 = dict()
	for i in range(n):
		if not d2.get(a[i]):
			d2.setdefault(a[i], 1)
			prev = d1[a[i]]
			a[i] = -1
			while not d2.get(prev):
				d2.setdefault(prev, 1)
				prev = d1[prev]
			c += 1
	print(power(2, c, mod))


import math
import heapq
import sys
import bisect
from collections import deque
import time
input = sys.stdin.readline
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	l = inlt()
	m = inlt()
	d = {}
	for i in range(n):
		d[l[i]] = m[i]
	x = 0
	v = [0] * n
	for i in range(n):
		if not v[i]:
			x += 1
			a = i + 1
			v[i] = 1
			while d[a] - 1 != i:
				a = d[a]
				v[a - 1] = 1
	print(pow(2, x, mod))


def solve(l):
	v = {i: False for i in l}

	def dfs(x):
		q = [x]
		while len(q) != 0:
			temp = q[0]
			q.pop(0)
			if v[l[temp]]:
				continue
			v[l[temp]] = True
			q.append(l[temp])
	ns = 0
	for i in l:
		if v[i]:
			continue
		dfs(i)
		ns += 1
	return ns
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = {}
	for i in range(n):
		l[a[i]] = b[i]
	t = solve(l)
	print(pow(2, t, mod))


from sys import stdin, stdout
import math, bisect, heapq
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
	return ''.join(list(map(str, a)))

def solve():
	n = I()
	a = L()
	b = L()
	d = {}
	for i in range(n):
		d[a[i]] = b[i]
	ans = 0
	mod = 10 ** 9 + 7
	c = [0] * n
	for i in range(1, n + 1):
		if c[i - 1]:
			continue
		ans += 1
		x = d[i]
		c[i - 1] = 1
		while i != x:
			c[x - 1] = 1
			x = d[x]
	print(pow(2, ans, mod))
for _ in range(I()):
	solve()


rr = int(input())
for g in range(rr):
	n = int(input())
	arr1 = list(map(int, input().split(' ')))
	arr2 = list(map(int, input().split(' ')))
	arr3 = [[0, False] for i in range(n)]
	for i in range(n):
		arr3[arr1[i] - 1][0] = arr2[i]
	t = 1
	for i in range(n):
		if arr3[i][1]:
			continue
		k = arr3[i][0] - 1
		arr3[i][1] = True
		while k != i:
			arr3[k][1] = True
			k = arr3[k][0] - 1
		t *= 2
		t %= 1000000007
	print(t)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split()
	b = input().split()
	d = dict(zip(a, b))
	count = 0
	mod = 10 ** 9 + 7
	while d:
		count += 1
		(k, v) = d.popitem()
		while v != k:
			v = d.pop(v)
	print(pow(2, count, mod))


import sys
input = iter(sys.stdin.read().splitlines()).__next__
MOD = 10 ** 9 + 7

def exp(n):
	x = 1
	for i in range(n):
		x *= 2
		if x > MOD:
			x -= MOD
	return x

def solve():
	n = int(input())
	lines = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(2)]
	graph = [None] * n
	for i in range(n):
		graph[lines[0][i]] = lines[1][i]
	num_cycles = 0
	cycle_not_found = set(range(n))
	while cycle_not_found:
		num_cycles += 1
		node = cycle_not_found.pop()
		current_node = graph[node]
		while current_node != node:
			cycle_not_found.remove(current_node)
			current_node = graph[current_node]
	return exp(num_cycles)
t = int(input())
output = []
for _ in range(t):
	output.append(solve())
print(*output, sep='\n')


def nPossibleConfigurations(puzzleLength, puzzle):
	nConfigurations = 1
	for row1_value in range(1, puzzleLength):
		if row1_value in puzzle:
			row2_value = puzzle.pop(row1_value)
			while row2_value != row1_value:
				row2_value = puzzle.pop(row2_value)
			nConfigurations = nConfigurations * 2 % 1000000007
	return nConfigurations

def testCase_1534c():
	return (int(input()), {v1: v2 for (v1, v2) in zip(map(int, input().split()), map(int, input().split()))})
tuple((print(nPossibleConfigurations(*testCase_1534c())) for x in range(int(input()))))


for _ in range(int(input())):
	n = input()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mask = [0] * len(a)
	d = {}
	for i in range(len(b)):
		d[b[i]] = i
	ans = 0
	for i in range(len(a)):
		if mask[i] == 0:
			mask[i] = 1
			s = set()
			s.add(a[i])
			x = i
			while len(s) != len(a):
				x = d[a[x]]
				mask[x] = 1
				if a[x] in s:
					break
				s.add(a[x])
			ans += 1
	print(pow(2, ans, 10 ** 9 + 7))


import sys

def dfs(g, vis, u):
	st = [u]
	vis[u] = 1
	while st:
		p = st.pop()
		vis[p] = 1
		for to in g[p]:
			if not vis[to]:
				st.append(to)
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	g = [[] for i in range(n)]
	for i in range(n):
		g[l1[i] - 1].append(l2[i] - 1)
		g[l2[i] - 1].append(l1[i] - 1)
	no = 0
	vis = [False] * (n + 1)
	for i in range(n):
		if vis[i] == False:
			dfs(g, vis, i)
			no += 1
	m = 10 ** 9 + 7
	print(pow(2, no, m))


mod = 10 ** 9 + 7

def fun():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	pairs = {}
	for i in range(n):
		pairs[a[i]] = b[i]
	ans = 0
	check = [True] * (n + 1)
	for i in range(n):
		k = a[i]
		if check[k]:
			check[k] = False
			v = pairs[k]
			check[v] = False
			while pairs[v] != k:
				v = pairs[v]
				check[v] = False
			ans += 1
	print(pow(2, ans, mod))
for _ in range(int(input())):
	fun()


def solve(permutation, n):
	visited = [False] * n
	cycles_count = 0
	for i in range(n):
		current = i
		if not visited[current]:
			cycles_count += 1
		while not visited[current]:
			visited[current] = True
			current = permutation[current]
	return 2 ** cycles_count
t = int(input())
MODULO = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	perm1 = list(map(lambda x: int(x) - 1, input().split()))
	perm2 = list(map(lambda x: int(x) - 1, input().split()))
	permutation = [0] * n
	for i in range(n):
		permutation[perm1[i]] = perm2[i]
	print(solve(permutation, n) % MODULO)


for _ in range(int(input())):
	count = 0
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dicio = dict()
	while count != n:
		dicio[a[count]] = b[count]
		count += 1
	(valorDado, contador, matriz) = (1000000007, 0, [0] * n)
	for i in range(1, n + 1):
		if matriz[i - 1]:
			continue
		posicaoAtual = dicio[i]
		matriz[i - 1] = 1
		contador += 1
		while posicaoAtual != i:
			matriz[posicaoAtual - 1] = 1
			posicaoAtual = dicio[posicaoAtual]
	print(pow(2, contador, valorDado))


import math

def task():
	n = int(input())
	grid = []
	grid.append(list(map(int, input().split())))
	grid.append(list(map(int, input().split())))
	pos = {}
	done = set()
	for i in range(n):
		e = grid[0][i]
		pos[e] = i
	c = 0
	for i in range(n):
		e = grid[1][i]
		if e in done:
			continue
		c += 1
		temp = e
		done.add(temp)
		temp = grid[1][pos[e]]
		while temp != e:
			done.add(temp)
			temp = grid[1][pos[temp]]
	print(2 ** c % (10 ** 9 + 7))
t = int(input())
for _ in range(t):
	task()


import sys
sys.setrecursionlimit(100000000)

def put(n):
	global d1
	global an
	f = d1[n]
	if f == 'stop':
		return 5
	d1[n] = 'stop'
	if d1[f] == 'stop':
		an = an * 2 % (10 ** 9 + 7)
		return 1
	put(f)
for ij in range(int(input())):
	d1 = {}
	an = 1
	n = int(input())
	f = list(map(int, input().split()))
	s = list(map(int, input().split()))
	for i in range(len(f)):
		d1[f[i]] = s[i]
	bil = set()
	for i in range(1, n + 1):
		sei = 'dd'
		if i not in bil:
			an = an * 2 % (10 ** 9 + 7)
			sei = i
			while sei not in bil:
				bil.add(sei)
				sei = d1[sei]
	print(an)


t = int(input())
mod = 10 ** 9 + 7
vis = []
for _ in range(t):
	n = int(input())
	a = []
	a.append(list(map(int, input().split())))
	a.append(list(map(int, input().split())))
	vis = [0 for i in range(n + 1)]
	e = {}
	d = 0
	for i in range(n):
		e[a[0][i]] = a[1][i]
	for i in range(1, n + 1):
		if vis[i]:
			pass
		else:
			d += 1
			x = i
			while not vis[x]:
				vis[x] = 1
				x = e[x]
	print(pow(2, d, mod))


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 1
	total = 0
	d = dict(zip(list(map(int, input().split(' '))), list(map(int, input().split(' ')))))
	(x, y) = d.popitem()
	while len(d) > 0:
		if y == x:
			ans += 1
			(x, y) = d.popitem()
		else:
			y = d.pop(y)
	total = 2 ** ans
	print(total % (10 ** 9 + 7))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
	(components, visited) = ([], [False] * n)

	def dfs(start):
		(component, stack) = ([], [start])
		while stack:
			start = stack[-1]
			if visited[start]:
				stack.pop()
				continue
			else:
				visited[start] = True
				component.append(start)
			for i in graph[start]:
				if not visited[i]:
					stack.append(i)
		return component
	for i in range(n):
		if not visited[i]:
			components.append(dfs(i))
	return components
for _ in range(int(input()) if True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	graph = [[] for i in range(n + 1)]
	for i in range(n):
		graph[a[i]] += [b[i]]
		graph[b[i]] += [a[i]]
	cp = connected_components(n + 1, graph)
	print(pow(2, len(cp) - 1, 10 ** 9 + 7))


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)

def Ii():
	return int(input())

def lint():
	return list(map(int, input().split()))

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a / gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 0
	right = len(a)
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num
t = Ii()
for _ in range(t):
	n = Ii()
	s1 = lint()
	s2 = lint()
	d = []
	d = [[s1[i], s2[i]] for i in range(n)]
	d.sort()
	vis = [0 for i in range(n)]
	(cnt, tmp, num) = (0, 1, 0)
	tot = set()
	while len(tot) != n:
		if vis[tmp - 1]:
			tmp += 1
			if num:
				cnt += 1
				num = 0
		else:
			vis[tmp - 1] = 1
			tot.add(d[tmp - 1][0])
			tmp = d[tmp - 1][1]
			num += 1
	print(2 ** (cnt + 1) % mod)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ans = 1
	flag = False
	indexes_a = [0 for x in range(n + 1)]
	visited = [False for x in range(n + 1)]
	for i in range(n):
		indexes_a[a[i]] = i
		if a[i] == b[i]:
			flag = True
			break
	if flag:
		print(0)
		continue
	for i in range(n):
		if visited[i]:
			continue
		temp = i
		while True:
			visited[temp] = True
			temp = indexes_a[b[temp]]
			if b[temp] == a[i]:
				visited[temp] = True
				ans = ans * 2 % (10 ** 9 + 7)
				break
	print(ans)


import os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(input())

def In():
	return map(int, input().split())

def ln():
	return list(map(int, input().split()))

def Sn():
	return input().strip()
BUFSIZE = 8192

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def solve():
	n = I()
	a = list(In())
	b = list(In())
	gp = defaultdict(set)
	visit = [False]
	for i in range(n):
		gp[a[i]].add(b[i])
		visit.append(False)
	power = 0
	for i in range(1, n + 1):
		if visit[i] == False:
			q = deque([i])
			power += 1
			while q:
				node = q.popleft()
				if visit[node] == True:
					continue
				visit[node] = True
				for x in gp[node]:
					if not visit[x]:
						q.append(x)
	print(pow(2, power, P))
	pass

def main():
	T = I()
	for i in range(T):
		solve()
M = 998244353
P = 1000000007

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
inf = float('inf')
mod = 1000000007

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

def inputt():
	return map(int, sys.stdin.readline().split())

def inputi():
	return int(sys.stdin.readline())

def inputs():
	return sys.stdin.readline()

def main():
	t = inputi()
	for _ in range(t):
		n = inputi()
		a = [0] + inputl()
		b = [0] + inputl()
		c = [0] * (n + 1)
		vis = [0] * (n + 1)
		ans = 1
		for i in range(1, n + 1):
			c[a[i]] = b[i]
		for i in range(1, n + 1):
			if vis[i] == 0:
				vis[i] = 1
				j = c[i]
				while j != i:
					vis[j] = 1
					j = c[j]
				ans = ans * 2 % mod
		print(ans)
main()


import math

def main_function():
	test_cases = range(int(input()))
	for test_case in test_cases:
		n = int(input())
		a = [int(j) for j in input().split(' ')]
		hash_a = [0 for i in range(n + 1)]
		b = [int(k) for k in input().split(' ')]
		for i in range(len(a)):
			hash_a[a[i]] = i
		counter = 0
		is_already_used = [False for i in range(len(a))]
		for i in range(n):
			if not is_already_used[i]:
				real_start = a[i]
				end = b[i]
				is_already_used[i] = True
				while real_start != end:
					index_i = hash_a[end]
					is_already_used[index_i] = True
					end = b[index_i]
				else:
					counter += 1
		if counter == 1:
			print(2)
		else:
			print(2 ** counter % (10 ** 9 + 7))
main_function()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a1 = [int(i) for i in input().split(' ')]
	a2 = [int(i) for i in input().split(' ')]
	s = sorted(zip(a1, a2))
	ch = [0] * n
	k = 0
	f = True
	while f:
		for i in range(n):
			if ch[i] == 0:
				ch[i] = 1
				save = i
				startv = s[i][0]
				while s[i][1] != startv:
					i = s[i][1] - 1
					ch[i] = 1
				k += 1
				i = save
		else:
			f = False
	print(2 ** k % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
rs = []
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	for (x, y) in zip(a, b):
		d[x - 1] = y - 1
	c = 0
	used = [0] * n
	for i in range(n):
		if not used[i]:
			used[i] = 1
			if d[i] == i:
				continue
			q = d[i]
			while q != i:
				used[q] = 1
				q = d[q]
			c += 1
	rs.append(pow(2, c, MOD))
print(*rs, sep='\n')


I = input
for _ in [0] * int(I()):
	I()
	d = dict(zip(I().split(), I().split()))
	c = 0
	while d:
		c += 1
		(x, y) = d.popitem()
		while (y := d.pop(y, 0)):
			y
	print(pow(2, c, 10 ** 9 + 7))


import string
from collections import defaultdict, Counter
from math import sqrt, log10, log2, log, gcd, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations_with_replacement
import sys, io, os
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = 10 ** 9 + 7
inf = float('inf')

def get_list():
	return [int(i) for i in input().split()]

def yn(a):
	print('YES' if a else 'NO', flush=False)
t = 1
t = int(input())

def exists():
	for i in range(n):
		if l[i] == m[i]:
			return 1
	return 0
for i in range(t):
	n = int(input())
	l = get_list()
	m = get_list()
	dict = defaultdict(int)
	mul = 1
	if exists():
		print(0)
		continue
	else:
		for i in range(n):
			dict[l[i]] = m[i]
	visited = defaultdict(int)
	for i in range(1, n + 1):
		if visited[i] == 0:
			j = dict[i]
			visited[i] = 1
			visited[j] = 1
			while j != i:
				j = dict[j]
				visited[j] = 1
			mul = mul * 2 % mod
	print(mul)


mod = 10 ** 9 + 7
import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.child = {}
		self.directed = d
		self.total_edges = 0

	def addEdge(self, x, y):
		self.total_edges += 1
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root):
		queue = [root]
		queue = deque(queue)
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1

	def dfs(self, root):
		ans = [0] * n
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i != self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0] * self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i] == 0:
				q.append(i)
		while len(q) != 0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		if vis != self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue

	def eulertour(self, root):
		stack = [root]
		t = []
		vis = [0] * self.n
		while len(stack) != 0:
			element = stack[-1]
			if vis[element]:
				t.append(stack.pop())
				continue
			t.append(element)
			vis[element] = 1
			for i in self.graph[element]:
				if not vis[i]:
					self.parent[i] = element
					stack.append(i)
		c = {}
		ans = []
		for i in t:
			if i not in c:
				ans.append(i)
				c[i] = 1
			elif c[i] != 2:
				ans.append(i)
				c[i] += 1
		return ans

	def articulation_points(self):
		at = [0] * self.n
		order = self.eulertour(0)
		done = {}
		disc = [0] * self.n
		low = [0] * self.n
		time = 0
		for i in order:
			if i not in done:
				done[i] = 1
				if self.parent[i] != -1:
					disc[i] = time + 1
					time += 1
					low[i] = disc[i]
		after = {}
		for i in range(self.n):
			if self.parent[i] not in after:
				after[self.parent[i]] = [i]
			else:
				after[self.parent[i]].append(i)
		dfs_order = []
		done = {}
		for i in order[::-1]:
			if i not in done:
				done[i] = 1
			else:
				dfs_order.append(i)
		for i in dfs_order:
			for j in self.graph[i]:
				if i in after and j in after[i]:
					low[i] = min(low[i], low[j])
					if i == 0 and len(after[i]) > 1:
						at[i] = 1
					if i != 0 and low[j] >= disc[i]:
						at[i] = 1
				elif j != self.parent[i]:
					low[i] = min(low[i], disc[j])
		return at

	def eulerian_path(self):
		curr_path = [0]
		cycle = []
		while curr_path:
			node = curr_path[-1]
			if self.graph[node]:
				nxt = self.graph[node].pop()
				curr_path.append(nxt)
			else:
				cycle.append(curr_path.pop())
		return cycle[::-1]
for nt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	g = Graph(n, False)
	for i in range(n):
		g.addEdge(a[i] - 1, b[i] - 1)
	ans = 0
	vis = [0] * n
	for i in range(n):
		if not vis[i]:
			g.bfs(i)
			ans += 1
	print(pow(2, ans, mod))


T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = [0] * (n + 1)
	res = 1
	for i in range(n):
		d[a[i]] = b[i]
	i = 1
	while i <= n:
		if d[i] != 0:
			count = 0
			j = d[i]
			d[i] = 0
			while j != 0:
				jj = j
				j = d[j]
				d[jj] = 0
				count += 1
			res *= 2
		i += 1
	print(res % (10 ** 9 + 7))


iter = int(input())
for iters in range(iter):
	n = int(input())
	test_keys = [int(i) for i in input().split(' ')]
	test_values = [int(i) for i in input().split(' ')]
	dict_array = [0] * (n + 1)
	for (i, j) in enumerate(test_keys):
		dict_array[j] = test_values[i]
	array = [False] * (n + 1)
	number = 0
	for i in range(1, n + 1):
		if array[i] == False:
			array[i] = True
			found = False
			a = i
			start = a
			while found != True:
				b = dict_array[a]
				array[b] = True
				a = b
				if b == start:
					found = True
					number = number + 1
	print(2 ** number % (10 ** 9 + 7))


import os, sys, time, collections, math, pprint, itertools as it, operator as op, bisect as bs, functools as fn
(maxx, localsys, mod) = (float('inf'), 0, int(1000000000.0 + 7))
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)
ceil = lambda n, x: (n + x - 1) // x
(osi, oso) = ('/home/priyanshu/Documents/cp/input.txt', '/home/priyanshu/Documents/cp/output.txt')
if os.path.exists(osi):
	sys.stdin = open(osi, 'r')
	sys.stdout = open(oso, 'w')
input = sys.stdin.readline

def maps():
	return map(int, input().split())
sys.setrecursionlimit(500000)
for _ in range(int(input())):
	n = int(input())
	(a, b) = (list(maps()), list(maps()))
	(d, ans) = ({a[i]: b[i] for i in range(n)}, 0)
	while d:
		ans += 1
		(k, v) = d.popitem()
		while k != v:
			v = d.pop(v)
	print(pow(2, ans, mod))


def solve(la, lb):
	da = {a: i for (i, a) in enumerate(la)}
	s = set()
	c = 0
	for a in la:
		v = a
		c += v not in s
		while v not in s:
			s |= {v}
			v = lb[da[v]]
	return pow(2, c, int(1000000000.0 + 7))
for _ in '_' * int(input()):
	input()
	print(solve([*map(int, input().split())], [*map(int, input().split())]))


t = int(input())
for _ in range(t):
	n = int(input())
	s0 = list(map(int, input().split()))
	s1 = list(map(int, input().split()))
	p = [0] * n
	for i in range(n):
		p[s0[i] - 1] = s1[i] - 1
	b = [True] * n
	r = 0
	for i in range(n):
		if b[i]:
			r += 1
			j = i
			while b[j]:
				b[j] = False
				j = p[j]
	res = 1
	for i in range(r):
		res = 2 * res % 1000000007
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	up = {}
	visited = set(a)
	for i in range(n):
		up[a[i]] = b[i]
	ans = 1
	mod = int(1000000000.0 + 7)
	while visited:
		cr = visited.pop()
		ky = up[cr]
		visited.remove(ky)
		while cr != up[ky]:
			ky = up[ky]
			visited.remove(ky)
		ans *= 2
		ans %= mod
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	d = dict(zip(map(int, input().split()), map(int, input().split())))
	c = 0
	while d:
		c += 1
		(x, y) = d.popitem()
		while y != x:
			y = d.pop(y)
	print((1 << c) % int(1000000000.0 + 7))


import sys
IS_INTERACTIVE = False
input = input
if not IS_INTERACTIVE:
	(*data,) = sys.stdin.read().split('\n')[::-1]

	def input():
		return data.pop()

def fprint(*args, **kwargs):
	print(*args, **kwargs, flush=True)

def eprint(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
MODULO = 10 ** 9 + 7
answers = []
for _ in range(int(input())):
	n = int(input())
	(*arr1,) = map(int, input().split())
	(*arr2,) = map(int, input().split())
	mapper = [-1] * (n + 1)
	for i in range(n):
		mapper[arr1[i]] = i
	arr1 = [mapper[v] for v in arr1]
	arr2 = [mapper[v] for v in arr2]
	ans = 1
	mark = [0] * n
	del arr1
	ans = 1
	cur = 0
	cnt = 0
	for i in range(n):
		if not mark[i]:
			cur = 1
			p = i
			mark[p] = 1
			p = arr2[p]
			while p != i:
				mark[p] = 1
				p = arr2[p]
				cur += 1
			mark[p] = 1
			cnt += 1
	ans = pow(2, cnt, MODULO)
	answers.append(ans)
print('\n'.join(map(str, answers)))


import collections
import functools
import math
import random
import sys
import bisect
import io, os
input = sys.stdin.readline

def In():
	return map(int, input().split())

def f():
	(r, c) = In()
	count = [r] * c
	l = []
	for i in range(r):
		s = input().rstrip()
		for i1 in range(c):
			if s[i1] == '#' and count[i1] == r:
				count[i1] = i
		l.append(s)
	ans = 0
	for i in range(r):
		for i1 in range(c):
			if l[i][i1] == '#':
				if i1 and count[i1 - 1] <= i:
					continue
				if count[i1] != i:
					continue
				if i1 < c - 1 and count[i1 + 1] <= i:
					continue
				ans += 1
	print(ans)

def cnum():
	mod = int(1000000000.0) + 7
	for _ in range(int(input())):
		n = int(input())
		count = [[] for _ in range(n)]
		l = input().split()
		l1 = input().split()
		for i in range(n):
			count[int(l[i]) - 1].append(int(l1[i]) - 1)
		his = [False] * n
		c = 0
		for i in range(n):
			if not his[i]:
				todo = [i]
				while todo:
					s = todo.pop()
					if his[s]:
						continue
					his[s] = True
					for i in count[s]:
						todo.append(i)
				c += 1
		res = 1
		x = 2
		while c:
			if c % 2 == 1:
				res = res * x % mod
			x = x * x % mod
			c //= 2
		print(res)
cnum()


a = int(input())
for x in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	d = list(map(int, input().split()))
	l = 1
	t = [0 for x in range(b)]
	for x in range(b):
		t[c[x] - 1] = d[x] - 1
	vis = [-1 for y in range(b)]
	l = 1
	o = []
	for x in range(b):
		if vis[c[x] - 1] == -1:
			if c[x] == d[x]:
				vis[c[x] - 1] = 1
			else:
				o.append(c[x] - 1)
				g = 1
				l = l * 2
				while g > 0:
					m = o.pop()
					g = 0
					vis[m] = 1
					if vis[t[m]] == 1:
						pass
					else:
						g = 1
						o.append(t[m])
	print(l % (10 ** 9 + 7))


import sys
import math
from typing import DefaultDict
mod = 10 ** 9 + 7
LI = lambda : [int(k) for k in input().split()]
input = lambda : sys.stdin.readline().rstrip()
IN = lambda : int(input())
S = lambda : input()
r = range

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for t in r(IN()):
	n = IN()
	r1 = LI()
	r2 = LI()
	di = dict()
	sm = 0
	nsm = 0
	df = []
	for i in range(n):
		di[r1[i]] = r2[i]
	for i in range(1, n + 1):
		if di[di[i]] == i:
			sm += 1
		else:
			df += [i]
	lp = DefaultDict(int)
	for ele in df:
		if lp[ele] == 0:
			fn = ele
			st = ele
			lp[st] = 1
			while di[st] != fn:
				st = di[st]
				lp[st] = 1
			nsm += 1
	sm //= 2
	ex = sm + nsm
	ans = power(2, ex, mod)
	ans = ans % mod
	print(ans)


t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	n = int(input())
	r1 = list(map(int, input().split()))
	r2 = list(map(int, input().split()))
	mat = dict(zip(r1, r2))
	cnt = 0
	while len(mat) != 0:
		cnt += 1
		d = mat.popitem()
		(a, b) = (d[0], d[1])
		while a != b:
			b = mat.pop(b)
	print(2 ** cnt % mod)


m = int(input())
c = 10 ** 9 + 7
for i in range(m):
	n = int(input())
	ar1 = list(map(int, input().split()))
	ar2 = list(map(int, input().split()))
	gr = dict()
	nv = set(ar1)
	for j in range(n):
		gr[ar1[j]] = ar2[j]
	result = 0
	while len(nv) != 0:
		a = nv.pop()
		temp = 0
		while a != temp:
			if temp == 0:
				temp = a
			temp = gr[temp]
			if a == temp:
				break
			nv.remove(temp)
		result += 1
	print(2 ** result % c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ll = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[l[i]] = ll[i]
	c = 0
	while len(d) > 0:
		for i in range(1, n + 1):
			if i in d:
				x = d[i]
				d.pop(i)
				while i != x:
					x = d.pop(x)
				c += 1
	print(2 ** c % (10 ** 9 + 7))


class Dsu:

	def __init__(this):
		this._parent = {}
		this._rank = {}

	def make_set(this, v):
		this._parent[v] = v
		this._rank[v] = 0

	def find_set(this, v):
		if this._parent[v] == v:
			return v
		this._parent[v] = this.find_set(this._parent[v])
		return this._parent[v]

	def union_set(this, a, b):
		a = this.find_set(a)
		b = this.find_set(b)
		if a != b:
			if this._rank[a] < this._rank[b]:
				(a, b) = (b, a)
			this._parent[b] = a
			if this._rank[a] == this._rank[b]:
				this._rank[a] += 1
MOD = int(1000000000.0 + 7)
t = int(input())
for tc in range(t):
	n = int(input())
	puz_top = list(map(int, input().split()))
	puz_bot = list(map(int, input().split()))
	dsu = Dsu()
	for i in range(1, n + 1):
		dsu.make_set(i)
	for i in range(n):
		dsu.union_set(puz_top[i], puz_bot[i])
	num_set = 0
	set_id = {}
	for i in range(1, n + 1):
		if dsu.find_set(i) in set_id:
			continue
		set_id[dsu.find_set(i)] = True
		num_set += 1
	result = 1
	for i in range(num_set):
		result = result * 2 % MOD
	print(result)


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

def read():
	return list(map(int, input().strip().split()))

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():

	def find(x):
		while par[x] != x:
			par[x] = par[par[x]]
			x = par[x]
		return x
	for _ in range(nin()):
		n = nin()
		mat = [read() for i in range(2)]
		par = [i for i in range(n + 1)]
		for i in range(n):
			par[find(mat[0][i])] = find(mat[1][i])
		st = set()
		for i in range(1, n + 1):
			st.add(find(i))
		ans_.append(pow(2, len(st), MOD))
solve()
for i in ans_:
	print(i)


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for _ in range(int(input())):
	n = int(input())
	f = 1
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d.update({a[i]: b[i]})
	for i in range(0, n):
		if a[i] == b[i]:
			print(0)
			f = 0
			break
	if f == 1:
		cnt = 0
		visited = [0 for i in range(0, n + 1)]
		fcnt = 0
		for i in d:
			v = d[i]
			cnt = 0
			while v != i and visited[i] == 0:
				visited[v] = 1
				v = d[v]
				if cnt == 0:
					fcnt = fcnt + 1
				cnt = 1
		ans = power(2, fcnt, 10 ** 9 + 7)
		print(ans % (10 ** 9 + 7))


from math import sqrt, gcd, ceil, floor, log, factorial
from itertools import permutations, combinations
from collections import Counter, defaultdict
import collections, sys, threading
sys.setrecursionlimit(10 ** 9)
threading.stack_size(10 ** 8)

def solve():

	def ii():
		return int(input())

	def si():
		return input()

	def mi():
		return map(int, input().split())

	def msi():
		return map(str, input().split())

	def li():
		return list(mi())

	def dfs(node, g, visited):
		visited[node] = 1
		for i in g[node]:
			if visited[i] == 0:
				dfs(i, g, visited)
	t = ii()
	for _ in range(t):
		n = ii()
		d1 = li()
		d2 = li()
		g = defaultdict(list)
		for i in range(n):
			g[d1[i]].append(d2[i])
			g[d2[i]].append(d1[i])
		visited = [0] * (n + 1)
		cnt = 0
		for i in range(1, n + 1):
			if visited[i] == 0:
				dfs(i, g, visited)
				cnt = (cnt + 1) % (10 ** 9 + 7)
		print(pow(2, cnt, 10 ** 9 + 7))
threading.Thread(target=solve).start()


def main():

	def input():
		return sys.stdin.readline().strip('\n')

	def I():
		return input()

	def II():
		return int(input())

	def MI():
		return map(int, input().split())

	def LI():
		return list(map(int, input().split()))

	def isPerfectSquare(x):
		return int(math.sqrt(x)) ** 2 == x
	sys.setrecursionlimit(500000)
	from collections import OrderedDict
	MOD = 10 ** 9 + 7

	def dfs(x):
		if not visited[x]:
			visited[x] = 1
			dfs(graph[x])
	for _ in range(II()):
		n = II()
		a = LI()
		b = LI()
		graph = {}
		visited = [0] * (n + 1)
		for i in range(n):
			graph[a[i]] = b[i]
		ans = 1
		for i in range(n):
			if visited[a[i]] == 0:
				dfs(a[i])
				ans = ans * 2 % MOD
		print(ans)
import sys, threading
import bisect
import math
import itertools
from sys import stdout
import heapq
from queue import PriorityQueue
sys.setrecursionlimit(2 ** 32 // 2 - 1)
threading.stack_size(1 << 27)
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a / gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 0
	right = len(a)
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num
t = I()
for _ in range(t):
	n = I()
	ar = defaultdict(lambda : [])
	vis = defaultdict(lambda : False)
	s = [lint(), lint()]
	for i in range(n):
		(a, b) = (s[0][i], s[1][i])
		ar[a].append(b)
		ar[b].append(b)
	cnt = 0
	for i in range(1, n + 1):
		if not vis[i]:
			cnt += 1
			store = [i]
			while len(store):
				tmp = store.pop()
				if not vis[tmp]:
					vis[tmp] = True
					for j in ar[tmp]:
						store.append(j)
	print(2 ** cnt % (10 ** 9 + 7))


for _ in range(int(input())):
	input()
	ls1 = [int(i) for i in input().split()]
	ls2 = [int(i) for i in input().split()]
	idx1 = {}
	idx2 = {}
	for i in range(len(ls1)):
		a = ls1[i]
		b = ls2[i]
		idx1[a] = b
		idx2[b] = a
	vis = set()
	ret = 0

	def dfs(start):
		now = start
		while True:
			nxt = idx1[idx1[now]]
			vis.add(now)
			vis.add(idx1[now])
			vis.add(nxt)
			if nxt == start:
				return True
			now = nxt
	for i in ls1:
		if i not in vis:
			dfs(i)
			ret += 1
	print(pow(2, ret, int(1000000000.0 + 7)))


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
from collections import defaultdict, deque
import heapq
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
MOD = pow(10, 9) + 7
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split(' ')))
	l2 = list(map(int, input().split(' ')))
	l = []
	for i in range(n):
		l.append((l1[i] - 1, l2[i] - 1))
	l.sort()
	visited = [False] * n
	c = 1
	for i in range(n):
		if visited[i]:
			continue
		c = c * 2 % MOD
		x = l[i][1]
		visited[i] = True
		while True:
			if visited[x]:
				break
			visited[x] = True
			x = l[x][1]
	print(c)


from collections import defaultdict
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	f = 1
	for i in range(n):
		if a[i] == b[i]:
			f = 0
			break
	if f == 0:
		print('0')
		continue
	one = defaultdict(int)
	two = defaultdict(int)
	for i in range(n):
		one[a[i]] = i
		two[b[i]] = i
	l = 0
	ans = [0] * (n + 1)
	for i in range(n):
		if ans[a[i]] == 1 and ans[b[i]] == 1:
			continue
		ans[a[i]] = 1
		lol = b[i]
		u = 0
		while ans[lol] != 1:
			ans[lol] = 1
			indi = one[lol]
			lol = b[indi]
		l += 1
	print(pow(2, l, mod))


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def main():
	for ik in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		l1 = list(map(int, input().split()))
		graph = defaultdict(list)
		for i in range(n):
			graph[l[i]].append(l1[i])
		visited = [False] * (n + 1)

		def dfs(v, visited):
			visited[v] = True
			for i in graph[v]:
				if visited[i] == False:
					dfs(i, visited)
		ans = 0
		for i in range(1, n + 1):
			if visited[i] == False:
				ans += 1
				dfs(i, visited)
		print(pow(2, ans, mod))
t = threading.Thread(target=main)
t.start()
t.join()


import sys
from collections import Counter

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
sys.setrecursionlimit(20000)

class U:

	def __init__(self, n):
		self.parent = {i: i for i in range(1, n + 1)}

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			self.parent[x] = self.find(self.parent[x])
			return self.parent[x]

	def union(self, x, y):
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root != y_root:
			self.parent[self.parent[y_root]] = self.parent[x_root]
T = int(input())
for _ in range(T):
	n = int(input())
	A = get_ints()
	B = get_ints()
	dp = U(n)
	for i in range(n):
		dp.union(A[i], B[i])
	for i in dp.parent:
		dp.parent[i] = dp.find(dp.parent[i])
	swappable_groups = len(set(dp.parent.values()))
	print(2 ** swappable_groups % (10 ** 9 + 7))


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
from bisect import *
from collections import defaultdict as dd
from collections import Counter as cc
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	n = int(input())
	a = inp()
	b = inp()
	d = {}
	for i in range(n):
		d[a[i]] = i
	ans = 0
	vis = [False] * n
	for i in range(n):
		if vis[i] == False:
			ele = a[i]
			num = b[i]
			while True:
				vis[d[num]] = True
				if b[d[num]] == ele:
					break
				else:
					num = b[d[num]]
			ans += 1
	print(pow(2, ans, mod))


import collections
import heapq
from bisect import bisect_right
import math
t = int(input())
for w in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	v = []
	for i in range(n):
		arr = [a[i], b[i], 0]
		v.append(arr)
	v.sort()
	count = 0
	for i in range(n):
		pos = i
		if v[i][2] == 1:
			continue
		while True:
			if v[pos][1] == v[i][0]:
				count += 1
				break
			else:
				pos = v[pos][1] - 1
				v[pos][2] = 1
	print(2 ** count % (10 ** 9 + 7))


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = defaultdict(int)
	for i in range(n):
		d[a[i]] = i
	res = 1
	check = [0] * n
	for i in range(n):
		if check[i]:
			continue
		num = b[i]
		check[i] = 1
		while num != a[i]:
			ind = d[num]
			num = b[ind]
			check[ind] = 1
		res = res * 2 % mod
	print(res)


T = int(input())
for ti in range(T):
	n = int(input())
	allset = set(range(n))
	visited = [0 for i in range(n)]
	row1 = [int(x) - 1 for x in input().split(' ')]
	row2 = [int(x) - 1 for x in input().split(' ')]
	adj = [[] for i in range(n)]
	for i in range(n):
		adj[row1[i]].append(row2[i])
	components = 0
	for i in range(n):
		if visited[i]:
			continue
		dfsstack = []
		dfsstack.append(i)
		components += 1
		while len(dfsstack) > 0:
			ele = dfsstack.pop()
			visited[ele] = True
			for nei in adj[ele]:
				if visited[nei]:
					continue
				else:
					dfsstack.append(nei)
	ans = 1
	for i in range(components):
		ans = 2 * ans % (10 ** 9 + 7)
	print(ans)


def findParent(elem):
	if parents[elem] == elem:
		return elem
	return findParent(parents[elem])

def union(elem1, elem2):
	child = min(elem1, elem2)
	parent = max(elem1, elem2)
	parents[child] = parent
for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	parents = [i for i in range(n + 1)]
	for i in range(n):
		(p1, p2) = (findParent(arr1[i]), findParent(arr2[i]))
		union(p1, p2)
	for i in range(1, n + 1):
		parents[i] = findParent(i)
	distinctParents = len(set(parents[1:]))
	print(pow(2, distinctParents, 10 ** 9 + 7))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, sys
from sys import stdin, stdout

def modinv(n, p):
	return pow(n, p - 2, p)

def nc():
	return map(int, ns().split())

def narr():
	return list(map(int, ns().split()))

def ns():
	return input()

def ni():
	return int(input())
t = ni()
for _ in range(t):
	n = ni()
	a = narr()
	b = narr()
	vis = [False] * n
	ind = [0] * n
	ans = 1
	mod = 1000000007
	for i in range(n):
		ind[a[i] - 1] = i
	for i in range(n):
		x = i
		if not vis[x]:
			ans = ans * 2 % mod
		while not vis[x]:
			vis[x] = True
			x = ind[b[x] - 1]
	print(ans)


import sys
import random
import time
input = sys.stdin.readline
MOD = int(1000000000.0) + 7
ans = []
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	A = list(map(int, input().strip().split()))
	B = list(map(int, input().strip().split()))
	mainB = [0] * (N + 1)
	calc = [0] * (N + 1)
	for (i, b) in enumerate(B):
		mainB[b] = A[i]
	unique = 0
	for i in range(1, N + 1):
		if calc[i] == 0:
			unique += 1
			j = mainB[i]
			calc[i] = 1
			while j != i:
				calc[j] = 1
				j = mainB[j]
	ans.append(str(pow(2, unique, MOD)))
print('\n'.join(ans))


for _ in range(int(input())):
	x = 0
	n = int(input())
	a = [list(map(int, input().split())) for col in range(2)]
	pairs = [0] * (n + 1)
	for i in range(n):
		pairs[a[0][i]] = a[1][i]
	marked = [False] * (n + 1)
	for i in range(1, n + 1):
		if not marked[i]:
			x += 1
			s = [i]
			while True:
				r = s.pop()
				marked[r] = True
				if not marked[pairs[r]]:
					s.append(pairs[r])
				else:
					break
	w = 1
	for i in range(x):
		w *= 2
		w %= 1000000007
	print(w)


test_case_num = int(input())
MODULE = 10 ** 9 + 7
for _ in range(test_case_num):
	n = int(input())
	cycles = 0
	first_line = []
	second_line = []
	first_dict = {}
	for (i, x) in enumerate(input().split()):
		first_line.append(x)
		first_dict[x] = i
	for (i, x) in enumerate(input().split()):
		second_line.append(x)
	used_nums = set()
	for (i, x) in enumerate(first_line):
		if x in used_nums:
			continue
		else:
			start = x
			end = second_line[i]
			used_nums.add(start)
			used_nums.add(end)
			cycles += 1
			while start != end:
				new_index = first_dict[end]
				end = second_line[new_index]
				used_nums.add(end)
	answer = 2 ** cycles % MODULE
	print(answer)


t = input()
mod = 1000000000.0 + 7
for i in range(int(t)):
	n = input()
	list_1 = input().split(' ')
	list_2 = input().split(' ')
	a = [False] * int(n)
	b = [0] * int(n)
	for i in range(int(n)):
		list_1[i] = int(list_1[i]) - 1
		list_2[i] = int(list_2[i]) - 1
		b[int(list_1[i])] = int(list_2[i])
	solution = 1
	x = 0
	for i in range(int(n)):
		if not a[i]:
			solution = solution * 2 % mod
			x = i
			while not a[x]:
				a[x] = True
				x = b[x]
	print(int(solution))


class UnionFind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [0] * n

	def Find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.Find(self.par[x])
			return self.par[x]

	def Unite(self, x, y):
		x = self.Find(x)
		y = self.Find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[y] += self.par[x]
				self.par[x] = y
			else:
				self.par[x] += self.par[y]
				self.par[y] = x
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def Same(self, x, y):
		return self.Find(x) == self.Find(y)

	def Size(self, x):
		return -self.par[self.Find(x)]
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	toid = {}
	for (i, a) in enumerate(A):
		toid[a] = i
	uf = UnionFind(n)
	for i in range(n):
		j = toid[B[i]]
		uf.Unite(i, j)
	cnt = 0
	for i in range(n):
		if uf.par[i] < 0:
			cnt += 1
	ans = pow(2, cnt, mod)
	print(ans % mod)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = dict(zip(a, b))
	cnt = 0
	while d:
		cnt += 1
		(k, v) = d.popitem()
		while v != k:
			v = d.pop(v)
	print(pow(2, cnt, 10 ** 9 + 7))


def solve(length, row1, row2):
	edges = {}
	for k in range(length):
		edges[row1[k]] = row2[k]
	cycles = 0
	visited = set([])
	for k in range(length):
		if row1[k] in visited:
			continue
		cycles += 1
		current = row1[k]
		while current not in visited:
			visited.add(current)
			current = edges[current]
	return 2 ** cycles % (10 ** 9 + 7)
tests = int(input())
for test in range(tests):
	length = int(input())
	row1 = [int(inp) for inp in input().split()]
	row2 = [int(inp) for inp in input().split()]
	print(solve(length, row1, row2))


import os
import sys
from io import BytesIO, IOBase
import math
from collections import Counter

def func(n, array1, array2):
	go = {}
	num_set = 0
	values = set(range(n))
	for (val1, val2) in zip(array1, array2):
		go[val1 - 1] = val2 - 1
	while values:
		val = values.pop()
		new_val = go[val]
		while new_val != val:
			tmp = new_val
			new_val = go[new_val]
			values.remove(tmp)
		num_set += 1
	return 2 ** num_set % (10 ** 9 + 7)

def main():
	num_test = int(parse_input())
	result = []
	for _ in range(num_test):
		n = int(parse_input())
		array1 = [int(i) for i in parse_input().split()]
		array2 = [int(i) for i in parse_input().split()]
		result.append(func(n, array1, array2))
	print('\n'.join(map(str, result)))
parse_input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	store = set()
	index = [0 for i in range(n + 1)]
	for i in range(n):
		index[a[i]] = i
	ans = 0
	for i in range(1, n + 1):
		if i not in store:
			x = b[index[i]]
			store.add(i)
			while x != i:
				store.add(x)
				x = b[index[x]]
			ans += 1
	print(pow(2, ans, 10 ** 9 + 7))


mas = list(map(int, input().split()))
t = mas[0]
for j in range(t):
	mas = list(map(int, input().split()))
	n = mas[0]
	mas1 = list(map(int, input().split()))
	mas2 = list(map(int, input().split()))
	dct = {mas1[i]: mas2[i] for i in range(n)}
	start = 2
	st = 1
	s = 0
	ok = True
	for i in range(n):
		st = dct.pop(st, -1)
		if st == -1:
			s += 1
			okk = True
			while okk:
				st = dct.pop(start, -1)
				start += 1
				if st != -1:
					okk = False
	pr = 1
	for i in range(s + 1):
		pr = pr * 2 % 1000000007
	if ok == True:
		print(pr)
	else:
		print(0)


t = int(input())
answers = list()
modulus = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	a = map(int, input().split())
	b = map(int, input().split())
	edges = dict()
	ans = 1
	for (i, j) in zip(a, b):
		edges[i] = j
	used = set(range(1, n + 1))
	while len(used) > 0:
		elem = used.pop()
		while edges[elem] in used:
			used.remove(edges[elem])
			elem = edges[elem]
		ans = ans * 2 % modulus
	answers.append(ans)
for k in range(t):
	print(answers[k])


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007
for _ in range(stdint()):
	n = stdint()
	a = stdarr()
	b = stdarr()
	groups = 0
	visited = [False] * n
	inda = {}
	indb = {}
	for i in range(n):
		inda[a[i]] = i
		indb[b[i]] = i
	for i in range(n):
		if not visited[i]:
			groups += 1
			start = a[i]
			next = b[i]
			visited[i] = True
			while next != start:
				ina = inda[next]
				next = b[ina]
				visited[ina] = True
	res = pow(2, groups, mod)
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = [0] * (n + 1)
	al = set()
	for i in range(1, n + 1):
		al.add(i)
	for i in range(n):
		s[a[i]] = b[i]
	cnt = 0
	for i in range(1, n + 1):
		if i not in al:
			continue
		else:
			last = i
			while last in al:
				al.discard(last)
				last = s[last]
			cnt += 1
	ans = 1
	for i in range(cnt):
		ans *= 2
		ans = ans % (10 ** 9 + 7)
	print(ans)


from collections import deque, defaultdict

def solve(n, a, b):
	d = {x: y for (x, y) in zip(a, b)}
	processed = [False for _ in range(n + 1)]
	result = 1
	modul = 10 ** 9 + 7
	for i in range(1, n + 1):
		if processed[i]:
			continue
		result *= 2
		result %= modul
		start = i
		curr = start
		while True:
			processed[curr] = True
			curr = d[curr]
			if curr == start:
				break
	return result
t = int(input())
results = deque()
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	result = solve(n, a, b)
	results.append(result)
for result in results:
	print(result)


mod = 10 ** 9 + 7

def solve(A, n):
	goto = {}
	for i in range(n):
		goto[A[0][i]] = A[1][i]
	cycle = 0
	done = [False] * (n + 1)
	for i in range(1, n + 1):
		if done[i]:
			continue
		cycle += 1
		while done[i] == False:
			nxt = goto[i]
			done[i] = True
			i = nxt
	return pow(2, cycle, mod)
for case in range(int(input())):
	n = int(input())
	A = []
	for i in range(2):
		li = list(map(int, input().split()))
		A.append(li)
	ans = solve(A, n)
	print(ans)


mod = 1000000007
t = int(input())
for i in range(t):
	count = 0
	n = int(input())
	q = input().split()
	w = input().split()
	a = [[int(q[j]), int(w[j])] for j in range(n)]
	a.sort()
	for j in range(n):
		if a[j][0] != 0:
			check = 0
			ini = a[j][0]
			while check == 0:
				a[j][0] = 0
				if a[j][1] == ini:
					count += 1
					check = 1
				else:
					j = a[j][1] - 1
	print(pow(2, count, mod))


import math
import sys

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

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

def input():
	return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7

def main():
	for _ in range(int(input())):
		n = int(input())
		a = get_array()
		b = get_array()
		vis = [False] * n
		ind_a = [-1] * (n + 1)
		for i in range(n):
			ind_a[a[i]] = i
		ans = 0
		for i in range(n):
			if vis[i]:
				continue
			ans += 1
			vis[i] = True
			val = b[i]
			while val != a[i]:
				next_ind = ind_a[val]
				vis[next_ind] = True
				val = b[next_ind]
		print(pow(2, ans, MOD))
main()


a = []
b = []
va = []
vb = []
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	va = [0] * (n + 1)
	vb = [0] * (n + 1)
	c = 0
	for i in range(n):
		if va[b[i]] == a[i]:
			c += 1
		elif va[b[i]] > 0 and vb[a[i]] > 0:
			vb[va[b[i]]] = vb[a[i]]
			va[vb[a[i]]] = va[b[i]]
		elif va[b[i]] > 0:
			va[a[i]] = va[b[i]]
			vb[va[b[i]]] = a[i]
		elif vb[a[i]] > 0:
			vb[b[i]] = vb[a[i]]
			va[vb[a[i]]] = b[i]
		else:
			va[a[i]] = b[i]
			vb[b[i]] = a[i]
	print(pow(2, c, 1000000007))


import sys
import io, os
import math
gcd = math.gcd
ceil = math.ceil
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
p = 10 ** 9 + 7

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a1 = list(map(int, input().split()))
		a2 = list(map(int, input().split()))
		found = [-1] * (n + 1)
		c = 0
		ind = [0] * (n + 1)
		for i in range(n):
			ind[a1[i]] = i
		for i in range(n):
			if found[a1[i]] == -1:
				init = a1[i]
				curr = a2[i]
				while curr != init:
					found[curr] = c
					curr = a2[ind[curr]]
				c += 1
		print(pow(2, c, p))
main()


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()
M = 10 ** 9 + 7
for _ in range(aint()):
	n = aint()
	a = alist()
	b = alist()
	d = {}
	for i in range(1, n + 1):
		d[i] = None
	for i in range(n):
		d[b[i]] = a[i]
	vis = [True] * (n + 1)
	cycles = 0
	for i in range(n):
		if vis[i + 1]:
			t = d[i + 1]
			r = 0
			while t != i + 1:
				r += 1
				vis[t] = False
				t = d[t]
			if r > 0:
				cycles += 1
	print(2 ** cycles % M)


import sys

def readnum():
	input = sys.stdin.readline
	a = list(map(int, input().split()))
	return a

def printf(val):
	sys.stdout.write(str(val) + '\n')

def power(a, b, mod):
	if b == 1:
		return a
	if b == 0:
		return 1
	ans = power(a, b // 2, mod)
	ans *= ans
	if b % 2:
		ans *= a
	ans = ans % mod
	return ans
t = readnum()[0]
for _ in range(t):
	n = readnum()[0]
	arr1 = readnum()
	arr2 = readnum()
	arr_rev = [0] * len(arr1)
	starting_points = set([i for i in range(len(arr1))])
	for i in range(len(arr1)):
		arr_rev[arr1[i] - 1] = i
	res = 0
	while len(starting_points) > 0:
		p = starting_points.pop()
		end_p = p
		next_p = -1
		while next_p != end_p:
			next_p = arr2[arr_rev[p]] - 1
			if next_p == end_p:
				break
			starting_points.remove(next_p)
			p = next_p
		res += 1
	print(power(2, res, 10 ** 9 + 7))


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr3 = [[0, False] for i in range(n)]
	for i in range(n):
		arr3[arr1[i] - 1][0] = arr2[i]
	ans = 1
	for i in range(n):
		if arr3[i][1]:
			continue
		k = arr3[i][0] - 1
		arr3[i][1] = True
		while k != i:
			arr3[k][1] = True
			k = arr3[k][0] - 1
		ans *= 2
		ans %= 1000000007
	print(ans)


from collections import defaultdict as dc, deque

def bfs(node, visited):
	visited[node] = True
	dq = deque([])
	dq.append(node)
	while dq:
		u = dq.popleft()
		for v in g[u]:
			if not visited[v]:
				visited[v] = True
				dq.append(v)
	return None
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	g = dc(set)
	exp = 0
	mod = 10 ** 9 + 7
	for i in range(n):
		g[a[i]].add(b[i])
		g[b[i]].add(a[i])
	visited = dc(bool)
	exp = 0
	for i in range(n):
		if not visited[i + 1]:
			exp += 1
			bfs(i + 1, visited)
	print(pow(2, exp, 10 ** 9 + 7))


import sys, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass
for _ in range(int(inp())):
	n = int(inp())
	A = [*map(int, inp().split())]
	B = [*map(int, inp().split())]
	C = [0] * (n + 1)
	D = [0] * n
	for (i, a) in enumerate(A):
		C[a] = i
	i = 0
	x = 0
	while i < n:
		if D[i] == 1:
			i += 1
		else:
			x += 1
			while D[i] == 0:
				D[i] = 1
				i = C[B[i]]
	print(2 ** x % 1000000007)


modulo = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	daf1 = list(map(int, input().split()))
	daf2 = list(map(int, input().split()))
	dct = dict()
	for i in range(n):
		dct[daf1[i]] = daf2[i]
	total = set()
	count = 0
	for i in range(1, n + 1):
		if i in total:
			continue
		count += 1
		subtotal = set()
		x = i
		subtotal.add(x)
		total.add(x)
		while True:
			if dct[x] in subtotal:
				break
			else:
				subtotal.add(dct[x])
				total.add(dct[x])
				x = dct[x]
	print(pow(2, count, modulo))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[a[i]] = b[i]
	v = [False] * (n + 1)
	x = 0
	for i in range(1, n + 1):
		if v[i] == False:
			s = [i]
			x += 1
			while True:
				r = s.pop()
				v[r] = True
				if v[d[r]] == False:
					s.append(d[r])
				else:
					break
	w = 1
	for i in range(x):
		w *= 2
		w %= 1000000007
	print(w)


from collections import defaultdict
MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	P1 = [int(x) for x in input().split()]
	P2 = [int(x) for x in input().split()]
	d = defaultdict(lambda : 0)
	seen = defaultdict(lambda : False)
	for i in range(n):
		d[P1[i]] = P2[i]
	cycles = 0
	i = 0
	while i < n:
		if seen[P1[i]]:
			i += 1
			continue
		seen[P1[i]] = True
		x = d[P1[i]]
		while x != P1[i]:
			seen[x] = True
			x = d[x]
		cycles += 1
	ans = 1
	for _ in range(cycles):
		ans = ans * 2 % MOD
	print(ans)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	an = list(map(int, sys.stdin.readline().split()))
	bn = list(map(int, sys.stdin.readline().split()))
	dic_a = [-1 for _ in range(n + 1)]
	dic_b = [-1 for _ in range(n + 1)]
	for i in range(n):
		dic_a[an[i]] = i
		dic_b[bn[i]] = i
	stack = []
	valued = [False for _ in range(n + 1)]
	ans = 0
	for i in range(1, n + 1):
		if not valued[an[i - 1]]:
			ans += 1
			stack.append((an[i - 1], 1))
			stack.append((bn[i - 1], 0))
			valued[an[i - 1]] = True
			valued[bn[i - 1]] = True
			while stack:
				(x, y) = stack.pop()
				if y:
					p = an[dic_b[x]]
					if not valued[p]:
						valued[p] = True
						stack.append((p, 1))
				else:
					p = bn[dic_a[x]]
					if not valued[p]:
						valued[p] = True
						stack.append((p, 0))
	print(2 ** ans % (10 ** 9 + 7))


import math
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
	return int(input())

def input_list():
	return input().split(' ')

def input_list_int():
	return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
	return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
	global_ans.append(a)

def solve():
	n = input_int()
	r1 = input_list_int()
	r2 = input_list_int()
	tmp = {}
	tmp_pos = {}
	for i in range(n):
		tmp[r1[i]] = r2[i]
		tmp_pos[r1[i]] = i
	add = {}
	mn = []
	for i in range(n):
		if i not in add:
			s = [i]
			item = r1[i]
			d = r2[i]
			add[i] = 1
			while d != item:
				p = tmp_pos[d]
				add[p] = 1
				s.append(p)
				d = tmp[d]
			mn.append(s)
	count = len(mn)
	ans = 1
	for i in range(count):
		ans *= 2
		ans %= MOD
	pr(ans)
query_count = 1
query_count = input_int()
while query_count:
	query_count -= 1
	solve()
for global_ans_line in global_ans:
	print(global_ans_line)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	bhai = dict([])
	for i in range(n):
		bhai[a[i]] = b[i]
	i_still_love_her = set([])
	kabtak = 0
	for i in a:
		if i not in i_still_love_her:
			i_still_love_her.add(i)
			jabtakhaijaan = bhai[i]
			i_still_love_her.add(jabtakhaijaan)
			while jabtakhaijaan != i:
				jabtakhaijaan = bhai[jabtakhaijaan]
				if jabtakhaijaan != i:
					i_still_love_her.add(jabtakhaijaan)
			kabtak += 1
	print(pow(2, kabtak, 1000000007))


def nPossibleConfigurations(row1_values, row2_values):
	puzzle = dict(zip(row1_values, row2_values))
	nConfigurations = 1
	for row1_value in row1_values:
		if row1_value in puzzle:
			row2_value = puzzle.pop(row1_value)
			while row2_value != row1_value:
				row2_value = puzzle.pop(row2_value)
			nConfigurations = nConfigurations * 2 % 1000000007
	return nConfigurations

def testCase_1534c():
	input()
	return (input().split(), input().split())
tuple((print(nPossibleConfigurations(*testCase_1534c())) for x in range(int(input()))))


t = int(input())
for _ in range(t):
	n = int(input())
	v1 = list(map(int, input().split()))
	v2 = list(map(int, input().split()))
	l = [0] * (n + 1)
	for i in range(n):
		l[v1[i]] = i
	c = [-1] * n
	w = -1
	ans = 1
	for i in range(n):
		sz = 0
		ptr = i
		if c[ptr] == -1:
			w += 1
		while c[ptr] == -1:
			c[ptr] = w
			ptr = l[v2[ptr]]
			sz += 1
		if sz > 0:
			ans *= 2
			ans %= 1000000007
	print(ans)


import sys
input = sys.stdin.readline

class DSU:

	def __init__(self, n):
		self.uf = {i: i for i in range(n)}
		self.rank = {i: 1 for i in range(n)}
		self.cnt = n

	def find(self, x):
		if self.uf[x] != x:
			self.uf[x] = self.find(self.uf[x])
		return self.uf[x]

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px != py:
			if self.rank[px] > self.rank[py]:
				(px, py) = (py, px)
			self.rank[py] += self.rank[px]
			self.uf[px] = py
			self.cnt -= 1
			return True
		return False
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	dsu = DSU(n)
	for (a, b) in zip(A, B):
		dsu.union(a - 1, b - 1)
	print(pow(2, dsu.cnt, 10 ** 9 + 7))


T = int(input())
for t in range(T):
	n = int(input())
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	par = dict()
	for i in A:
		par[i] = i
	for i in B:
		par[-i] = -i

	def find(u):
		if par[u] == u:
			return u
		par[u] = find(par[u])
		return par[u]

	def unite(u, v):
		x = find(u)
		y = find(v)
		if x < y:
			(u, v) = (v, u)
		par[x] = y
	for i in range(n):
		unite(A[i], -A[i])
		unite(A[i], -B[i])
	ct = dict()
	for i in range(n):
		ct[find(A[i])] = 1
	MOD = 10 ** 9 + 7
	ans = 1
	for i in ct:
		ans = 2 * ans % MOD
	print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	a = lis()
	co = 0
	b = lis()
	vis = [0] * (n + 1)
	d = {}
	for i in range(n):
		d[a[i]] = b[i]
	for i in range(n):
		if vis[a[i]] == 0:
			co += 1
			pa = a[i]
			vis[a[i]] = 1
			go = d[a[i]]
			while go != pa:
				vis[go] = 1
				go = d[go]
	print(pow(2, co, 1000000007))


import heapq, math
from collections import defaultdict, deque
from os import getcwd
import sys, os.path
if os.path.exists('C:/Users/Dhanush/Desktop/cp/input.txt'):
	sys.stdout = open('C:/Users/Dhanush/Desktop/cp/output.txt', 'w')
	sys.stdin = open('C:/Users/Dhanush/Desktop/cp/input.txt', 'r')
input = sys.stdin.readline
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	temp = [0 for _ in range(n)]
	ans = 1
	d1 = {}
	d2 = {}
	for i in range(n):
		(a, b) = (l1[i], l2[i])
		d1[a] = i
		d2[b] = i
	for i in range(n):
		if temp[i] == 0:
			ans = ans * 2 % mod
			j = i
			while temp[j] == 0:
				temp[j] = 1
				j = d1[l2[j]]
	print(ans)


import sys

def input():
	return sys.stdin.readline().strip()

def exp(n):
	t = 1
	for i in range(n):
		t = t * 2 % (10 ** 9 + 7)
	return t
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	grid = [a, b]
	pa = [0] * (n + 1)
	pb = [0] * (n + 1)
	for i in range(n):
		pa[a[i]] = i
		pb[b[i]] = i
	pgrid = [pa, pb]
	visited = [False] * n
	groups = 0
	for i in range(n):
		if not visited[i]:
			visited[i] = True
			start = i
			col = start
			row = 0
			l = 0
			while col != start or l == 0:
				col = pgrid[row][grid[1 - row][col]]
				l += 1
				visited[col] = True
			groups += 1
	print(exp(groups))


def dfs(node, edges, visited):
	stack = [node]
	while stack:
		node = stack.pop()
		if node not in visited:
			visited.add(node)
			for kid in edges[node]:
				stack.append(kid)

def solve(row1, row2, n, ans):
	mod = pow(10, 9) + 7
	edges = {}
	for i in range(1, n + 1):
		edges[i] = []
	indices1 = [-1] * (n + 1)
	indices2 = [-1] * (n + 1)
	for i in range(n):
		indices1[row1[i]] = i + 1
		indices2[row2[i]] = i + 1
	for i in range(n):
		edges[i + 1].append(indices2[row1[i]])
		edges[i + 1].append(indices1[row2[i]])
	visited = set()
	total = 0
	for i in range(1, n + 1):
		if i not in visited:
			dfs(i, edges, visited)
			total += 1
	ans.append(str(pow(2, total, mod)))

def main():
	t = int(input())
	ans = []
	for i in range(t):
		n = int(input())
		row1 = list(map(int, input().split()))
		row2 = list(map(int, input().split()))
		solve(row1, row2, n, ans)
	print('\n'.join(ans))
main()


t = int(input())
while t:
	t -= 1
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	(ans, vi, graph) = (0, [0] * (n + 1), {})
	for i in range(n):
		graph[x[i]] = y[i]
	for j in graph.keys():
		if vi[j]:
			continue
		else:
			ans += 1
			te = j
			while graph[te] != j:
				te = graph[te]
				vi[te] = 1
			vi[j] = 1
	res = 2 ** ans % 1000000007
	print(res)


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def pw(x, y):
	ans = 1
	while y:
		if y % 2:
			ans *= x
			y -= 1
			ans %= mod
		else:
			x *= x
			y //= 2
			x %= mod
	return ans

def bfs(i):
	d = deque()
	d.append(i)
	v[i] = 1
	while d:
		t = d.popleft()
		for j in a[t]:
			if not v[j]:
				v[j] = 1
				d.append(j)
for _ in range(int(input())):
	n = int(input())
	a1 = list(map(int, input().split()))
	b1 = list(map(int, input().split()))
	a = [[] for _ in range(n + 1)]
	for (x, y) in zip(a1, b1):
		a[x].append(y)
	v = [0] * (n + 1)
	ct = 0
	for i in range(1, n + 1):
		if not v[i]:
			bfs(i)
			ct += 1
	print(pw(2, ct))


import sys
import glob
from collections import defaultdict
sys.setrecursionlimit(1000000)
ONLINE_JUDGE = bool(glob.glob('input*.txt'))
if ONLINE_JUDGE:
	sys.stdin = open(glob.glob('input*.txt')[0], 'r')
for test_var in range(int(input())):
	graph = defaultdict(list)
	n = int(input())
	visited = [False] * (n + 1)
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	independent = 0
	for i in range(n):
		graph[arr1[i]].append(arr2[i])
		graph[arr2[i]].append(arr1[i])
	for num in arr1:
		if not visited[num]:
			stack = [num]
			while stack:
				u = stack.pop()
				visited[u] = True
				for v in graph[u]:
					if not visited[v]:
						stack.append(v)
			independent += 1
	print(pow(2, independent, 10 ** 9 + 7))


from collections import defaultdict, deque
mod = pow(10, 9) + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	graph = defaultdict(list)
	cnt = 1
	for i in range(n):
		if a[i] == b[i]:
			cnt = 0
			break
		graph[a[i]].append(b[i])
	if cnt == 0:
		print(0)
		continue
	vis = [False] * (n + 1)
	for i in range(1, n + 1):
		if vis[i] == False:
			q = deque()
			q.append(i)
			while q:
				s = q.popleft()
				for nodes in graph[s]:
					if vis[nodes] == False:
						q.append(nodes)
						vis[nodes] = True
			cnt = cnt % mod * (2 % mod) % mod
	print(cnt)


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')
mod = int(1000000000.0 + 7)

def binary(a, b):
	res = 1
	while b:
		if b & 1:
			res = res * a % mod
		a = a * a % mod
		b //= 2
	return res

def solve():
	for _ in range(geta()):
		n = geta()
		a = getl()
		b = getl()
		index_a = {a[i]: i for i in range(n)}
		index_b = {b[i]: i for i in range(n)}
		need = {}
		ans = 0
		for i in range(n):
			if i in need:
				continue
			ans += 1
			q = deque()
			q.append(i)
			while q:
				now = q.popleft()
				if now in need:
					continue
				need[now] = True
				one = index_b[a[now]]
				two = index_a[b[now]]
				if one not in need:
					q.append(one)
				if two not in need:
					q.append(two)
		print(binary(2, ans))
solve()


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'

def pw(n, k, mod=1000000007):
	power = 1
	while k > 0:
		if k % 2 == 1:
			power = power * n % mod
		k = k // 2
		n = n * n % mod
	return power
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	sora = sorted(enumerate(a), key=lambda x: x[1])
	sorb = sorted(enumerate(b), key=lambda x: x[1])
	c = [0 for i in range(n)]
	j = 1
	for i in range(n):
		if not c[i]:
			c[i] = j
			k = sora[b[i] - 1][0]
			while not c[k]:
				c[k] = j
				k = sora[b[k] - 1][0]
			j += 1
	print(pw(2, j - 1))


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		if Nodes[find(x)] < Nodes[find(y)]:
			Nodes[find(y)] += Nodes[find(x)]
			Nodes[find(x)] = 0
			Group[find(x)] = find(y)
		else:
			Nodes[find(x)] += Nodes[find(y)]
			Nodes[find(y)] = 0
			Group[find(y)] = find(x)
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	Group = [i for i in range(n + 1)]
	Nodes = [1] * (n + 1)
	for i in range(n):
		Union(A[i], B[i])
	ANS = 0
	for i in range(1, n + 1):
		if find(i) == i:
			ANS += 1
	print(pow(2, ANS, mod))


from collections import defaultdict

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		d = defaultdict(list)
		for i in range(n):
			d[a[i]].append(i)
			d[b[i]].append(i)
		taken = [0] * n
		count = 0
		for i in range(n):
			if taken[i] == 0:
				count += 1
				initial = a[i]
				taken[i] = 1
				j = i
				while a[i] != b[j]:
					tmp = d[b[j]]
					if tmp[0] != j:
						k = tmp[0]
					else:
						k = tmp[1]
					j = k
					taken[j] = 1
		ans = 1
		for i in range(count):
			ans = ans * 2 % (10 ** 9 + 7)
		print(ans)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.PA = [-1] * n

	def root(self, a):
		L = []
		while self.PA[a] >= 0:
			L.append(a)
			a = self.PA[a]
		for l in L:
			self.PA[l] = a
		return a

	def unite(self, a, b):
		(ra, rb) = (self.root(a), self.root(b))
		if ra != rb:
			if self.PA[rb] >= self.PA[ra]:
				self.PA[ra] += self.PA[rb]
				self.PA[rb] = ra
			else:
				self.PA[rb] += self.PA[ra]
				self.PA[ra] = rb

	def size(self, a):
		return -self.PA[self.root(a)]

	def groups(self):
		G = [[] for _ in range(self.n)]
		for i in range(self.n):
			G[self.root(i)].append(i)
		return [g for g in G if g]

	def groups_index(self):
		G = [[] for _ in range(self.n)]
		for i in range(self.n):
			G[self.root(i)].append(i)
		cnt = 0
		GG = []
		I = [-1] * self.n
		for i in range(self.n):
			if G[i]:
				GG.append(G[i])
				I[i] = cnt
				cnt += 1
		return (GG, I)

	def group_size(self):
		G = [[] for _ in range(self.n)]
		for i in range(self.n):
			G[self.root(i)].append(i)
		return [len(g) for g in G if g]
P = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	uf = UnionFind(N)
	A = [int(a) - 1 for a in input().split()]
	B = [int(a) - 1 for a in input().split()]
	for (a, b) in zip(A, B):
		uf.unite(a, b)
	print(pow(2, len(uf.groups()), P))


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1i = [0] * n
	l2i = [0] * n
	v = [0] * n
	c = 0
	for i in range(n):
		l1i[l1[i] - 1] = i
	for i in range(n):
		l2i[l2[i] - 1] = i
	for j in range(n):
		if v[j] == 0:
			v[j] = 1
			a1 = l1[j]
			a2 = l2[j]
			v[j] = 1
			c += 1
			while a1 != -1 and a2 != -1:
				if a1 != -1:
					i2 = l2i[a1 - 1]
					if v[i2] == 0:
						v[i2] = 1
						p = l1[i2]
					else:
						p = -1
				if a2 != -1:
					i1 = l1i[a2 - 1]
					if v[i1] == 0:
						v[i1] = 1
						q = l2[i1]
					else:
						q = -1
				a1 = p
				a2 = q
	ans = 1
	for i in range(c):
		ans = 2 * ans % 1000000007
	print(ans)