#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.14159265

ll mod = 1000000007;
ll z   = 1000000000;
const ll N   = 1e5 + 1;
const ll INF = 1e18;
// ll mod = 998244353;


#define mp                make_pair
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (ll)((x).size())
#define fr                first
#define sc                second
#define pii               pair<ll,ll>
#define vi                vector<ll>
#define vvi               vector<vector<ll>>
#define vp                vector<pair<ll,ll>>
#define rep(i,a,b)        for(ll i=a;i<b;i++)
#define repr(i,a,b)       for(ll i=b-1;i>=a;i--)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll

template<typename T, typename T1>T amax(T &a, T1 b) {if (b > a)a = b; return a;}
template<typename T, typename T1>T amin(T &a, T1 b) {if (b < a)a = b; return a;}

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

// ll euclideandis(ll a, ll b)
// {
// 	return sqrt(a*a + b*b);
// }
// ll sumofdigit(ll a){ll final = 0;while(a){final += a%10;a = a/10;}return final;}

// bool cmp(const pair<ll,ll>& p1, const pair<ll,ll>& p2)
// {
// 	if(p1.first == p2.first)
// 	{
// 		return (p1.second > p2.second);
// 	}
// 	return (p1.first < p2.first);
// }

// int gcd(int a, int b)
// {
//     if (!a)
//        return b;
//     return gcd(b%a,a);
// }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////Sieve ////////////////////////////////////////////////////////
// ll prime[N + 1];
// void SieveOfEratosthenes()
// {
// 	fill(prime, prime + N, -1);

// 	for (ll p = 2; p * p <= N; p++)
// 	{
// 		if (prime[p] == p)
// 		{
// 			for (ll i = p * p; i <= N; i += p)
// 				prime[i] = p;
// 		}
// 	}
// 	// for (ll p = 2; p <= n; p++)
// 	//     if (prime[p])
// 	//         cout << p << " ";
// }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////Factorial and inverse modulo calc//////////////////////////////
// vector<ll> fact(1000001,0);
// fact[0] = 1;
// for(int i=1;i<=1000000;i++)
//     fact[i] = (fact[i-1]*i)%mod;

// vector<ll> inv(1000001,0);
// inv[0]=1;
// for(int i=1;i<=1000000;i++)
// {
//     inv[i]=(inv[i-1]*powe(i,mod-2))%mod;
// }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////exponential power calc//////////////////////////////////////////
ll powe(ll x, ll y)
{
	if (y == 0) return 1;
	if (y == 1) return x;

	ll t = powe(x, y / 2);
	t = (t * t) % mod;

	if (y % 2 == 1) t = (t * x) % mod;

	return t;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////Fenwick Tree (BIT)(1-based)/////////////////////////////////////
// vi BIT; // set size for array
// ll get_sum(ll index) // returns sum of range 1 to index.(1 based indexing)
// {
// 	ll sum = 0;
// 	for(;index>0;index -= (index&-index))
// 	{
// 		sum += BIT[index];
// 	}
// 	return sum;
// }
// void update(ll index, ll val) // just updates , does not replace
// {
// 	for(;index<=n; index += (index&-index))
// 	{
// 		BIT[index] += val;
// 	}
// }

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////Fenwick Tree (BIT)(0-based)/////////////////////////////////////
// ll get(vi& BIT, ll index) // returns sum of range 0 to index-1.(0 based indexing)
// {
// 	ll sum = 0;
// 	for(;index>=0;index = (index & (index+1))-1)
// 	{
// 		sum += BIT[index];
// 	}
// 	return sum;
// }
// void update(vi& BIT, ll index, ll val) // just updates , does not replace
// {
// 	for(;index<BIT.size(); index |= (index+1))
// 	{
// 		BIT[index] += val;
// 	}
// }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////fibonacii//////////////////////////////////////////////////////////
// vi fib(100005);
// void fibo()
// {
// 	fib[0] = 1;fib[1] = 1;fib[2] = 2;
// 	for(int i=3;i<=10000;i++)
// 		fib[i] = (fib[i-1]%mod+fib[i-2]%mod)%mod;
// }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////DFS, Dijkstra and calc of which path was travelled more////////////
// void DFS(pii end)
// {
// 	queue<pii> q;
// 	q.push(end);
// 	int movex[] = {1,0,-1,0};
// 	int movey[] = {0,1,0,-1};
// 	while(!q.empty())
// 	{
// 		pii p = q.front();
// 		q.pop();
// 		int x = p.fr;
// 		int y = p.sc;
// 		rep(i,0,4)
// 		{
// 			int X = x + movex[i];
// 			int Y = y + movey[i];
// 			if(X>=0 && X<r && Y>=0 && Y<c && !visited[X][Y] && a[X][Y] != 'T')
// 			{
// 				dist[X][Y] = min(dist[X][Y], dist[x][y] + 1);
// 				q.push(mp(X,Y));
// 			}
// 		}
// 	}
// }

// vector<bool> visited(N, false);
// vector<vector<pair<ll,ll>>> adj(N);
// vector<pair<ll,ll>> edges;
// vector<ll> dist(N,INT_MAX);
// void dijkstra(ll start, ll n)
// {
// 	set<pair<ll,ll>> s;
// 	s.insert(mp(0,start));
// 	while(!s.empty())
// 	{
// 		pii p = *s.begin();
// 		s.erase(s.begin());
// 		for(pii u:adj[p.sc])
// 		{
// 			ll to = u.fr;
// 			ll time = u.sc;
// 			if(dist[to] > dist[p.sc]+time)
// 			{
// 				s.erase({dist[to], to});
// 				dist[to] = dist[p.sc]+time;
// 				s.insert({dist[to], to});
// 			}
// 		}
// 	}
// }

// ll dfs(priority_queue<ll>& pq, vvi& adj, ll start, ll par)
// {
// 	ll sum = 1;
// 	for(auto u:adj[start])
// 	{
// 		if(u != par)
// 		{
// 			ll x = dfs(pq, adj, u, start);
// 			pq.push((adj.size()-x)*x);
// 			sum += x;
// 		}
// 	}
// 	return sum;
// }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////// DSU /////////////////////////////////////////////////////////////////

// void make_set(int v) {
//     parent[v] = v;
//     rank[v] = 0;
// }

// int find_set(int v) {
//     if (v == parent[v])
//         return v;
//     return parent[v] = find_set(parent[v]);
// }

// void union_sets(int a, int b) {
//     a = find_set(a);
//     b = find_set(b);
//     if (a != b) {
//         if (rank[a] < rank[b])
//             swap(a, b);
//         parent[b] = a;
//         if (rank[a] == rank[b])
//             rank[a]++;
//     }
// }

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////// segment tree, (l,r) queries from 0 to r-1, 0 based indexing ///////////////////
// struct segtree{
// 	ll size;
// 	vector<ll> segtree;

// 	void init(ll n)
// 	{
// 		size = 1;
// 		while(size<n)
// 		{
// 			size*=2;
// 		}
// 		segtree.assign(2*size,INT_MAX);
// 	}
// 	void build(vector<ll>& a, ll x, ll lx, ll rx)
// 	{
// 		if(rx-lx == 1)
// 		{
// 			if(lx < a.size())
// 			{
// 				segtree[x] = a[lx];
// 			}
// 			return;
// 		}
// 		ll mid = (lx+rx)/2;
// 		build(a,2*x+1,lx,mid);
// 		build(a,2*x+2,mid,rx);
// 		segtree[x] = min(segtree[2*x+1],segtree[2*x+2]);
// 	}
// 	void build(vector<ll>& a)
// 	{
// 		build(a,0,0,size);
// 	}
// 	ll query(ll l, ll r,ll x, ll lx, ll rx)
// 	{
// 		if(r<=lx || l>=rx)
// 			return INT_MAX;
// 		if(r>=rx && l<=lx)
// 			return segtree[x];
// 		ll m = (lx+rx)/2;
// 		ll left = query(l,r,2*x+1,lx,m);
// 		ll right = query(l,r,2*x+2,m,rx);
// 		return min(left,right);

// 	}
// 	ll query(ll l, ll r)
// 	{
// 		return query(l,r,0,0,size);
// 	}
// };
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

ll t, n, m;

void solve()
{
	cin >> n;
	vi a(n), b(n);
	vi va(n, 0);
	map<ll, ll> pos;
	rep(i, 0, n)
	{
		cin >> a[i];
		pos[a[i]] = i;
	}
	rep(i, 0, n)
	{
		cin >> b[i];

	}
	int ans = 0;
	rep(i, 0, n)
	{
		if (va[i] == 0)
		{
			ll j = i;
			while (va[j] == 0)
			{
				va[j] = 1;
				j = pos[b[j]];
			}
			ans = (ans + 1) % mod;
		}
	}
	ll v = powe(2, ans);
	cout << v << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	cin >> t;
	// t = 1;
	while (t--)
	{
		solve();
	}
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 × n grid where each row is a permutation of the numbers 1,2,3,…,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 ≤ t ≤ 10^4). Description of the test cases follows.

The first line of each test case contains a single integer n (2 ≤ n ≤ 4 ⋅ 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,…,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 ⋅ 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.

Example

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. 

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.14159265

ll mod = 1000000007;
ll z   = 1000000000;
const ll N   = 1e5 + 1;
const ll INF = 1e18;
// ll mod = 998244353;


#define mp                make_pair
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (ll)((x).size())
#define fr                first
#define sc                second
#define pii               pair<ll,ll>
#define vi                vector<ll>
#define vvi               vector<vector<ll>>
#define vp                vector<pair<ll,ll>>
#define rep(i,a,b)        for(ll i=a;i<b;i++)
#define repr(i,a,b)       for(ll i=b-1;i>=a;i--)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll

template<typename T, typename T1>T amax(T &a, T1 b) {if (b > a)a = b; return a;}
template<typename T, typename T1>T amin(T &a, T1 b) {if (b < a)a = b; return a;}

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

// ll euclideandis(ll a, ll b)
// {
// 	return sqrt(a*a + b*b);
// }
// ll sumofdigit(ll a){ll final = 0;while(a){final += a%10;a = a/10;}return final;}

// bool cmp(const pair<ll,ll>& p1, const pair<ll,ll>& p2)
// {
// 	if(p1.first == p2.first)
// 	{
// 		return (p1.second > p2.second);
// 	}
// 	return (p1.first < p2.first);
// }

// int gcd(int a, int b)
// {
//     if (!a)
//        return b;
//     return gcd(b%a,a);
// }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////Sieve ////////////////////////////////////////////////////////
// ll prime[N + 1];
// void SieveOfEratosthenes()
// {
// 	fill(prime, prime + N, -1);

// 	for (ll p = 2; p * p <= N; p++)
// 	{
// 		if (prime[p] == p)
// 		{
// 			for (ll i = p * p; i <= N; i += p)
// 				prime[i] = p;
// 		}
// 	}
// 	// for (ll p = 2; p <= n; p++)
// 	//     if (prime[p])
// 	//         cout << p << " ";
// }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////Factorial and inverse modulo calc//////////////////////////////
// vector<ll> fact(1000001,0);
// fact[0] = 1;
// for(int i=1;i<=1000000;i++)
//     fact[i] = (fact[i-1]*i)%mod;

// vector<ll> inv(1000001,0);
// inv[0]=1;
// for(int i=1;i<=1000000;i++)
// {
//     inv[i]=(inv[i-1]*powe(i,mod-2))%mod;
// }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////exponential power calc//////////////////////////////////////////
ll powe(ll x, ll y)
{
	if (y == 0) return 1;
	if (y == 1) return x;

	ll t = powe(x, y / 2);
	t = (t * t) % mod;

	if (y % 2 == 1) t = (t * x) % mod;

	return t;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////Fenwick Tree (BIT)(1-based)/////////////////////////////////////
// vi BIT; // set size for array
// ll get_sum(ll index) // returns sum of range 1 to index.(1 based indexing)
// {
// 	ll sum = 0;
// 	for(;index>0;index -= (index&-index))
// 	{
// 		sum += BIT[index];
// 	}
// 	return sum;
// }
// void update(ll index, ll val) // just updates , does not replace
// {
// 	for(;index<=n; index += (index&-index))
// 	{
// 		BIT[index] += val;
// 	}
// }

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////Fenwick Tree (BIT)(0-based)/////////////////////////////////////
// ll get(vi& BIT, ll index) // returns sum of range 0 to index-1.(0 based indexing)
// {
// 	ll sum = 0;
// 	for(;index>=0;index = (index & (index+1))-1)
// 	{
// 		sum += BIT[index];
// 	}
// 	return sum;
// }
// void update(vi& BIT, ll index, ll val) // just updates , does not replace
// {
// 	for(;index<BIT.size(); index |= (index+1))
// 	{
// 		BIT[index] += val;
// 	}
// }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////fibonacii//////////////////////////////////////////////////////////
// vi fib(100005);
// void fibo()
// {
// 	fib[0] = 1;fib[1] = 1;fib[2] = 2;
// 	for(int i=3;i<=10000;i++)
// 		fib[i] = (fib[i-1]%mod+fib[i-2]%mod)%mod;
// }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////DFS, Dijkstra and calc of which path was travelled more////////////
// void DFS(pii end)
// {
// 	queue<pii> q;
// 	q.push(end);
// 	int movex[] = {1,0,-1,0};
// 	int movey[] = {0,1,0,-1};
// 	while(!q.empty())
// 	{
// 		pii p = q.front();
// 		q.pop();
// 		int x = p.fr;
// 		int y = p.sc;
// 		rep(i,0,4)
// 		{
// 			int X = x + movex[i];
// 			int Y = y + movey[i];
// 			if(X>=0 && X<r && Y>=0 && Y<c && !visited[X][Y] && a[X][Y] != 'T')
// 			{
// 				dist[X][Y] = min(dist[X][Y], dist[x][y] + 1);
// 				q.push(mp(X,Y));
// 			}
// 		}
// 	}
// }

// vector<bool> visited(N, false);
// vector<vector<pair<ll,ll>>> adj(N);
// vector<pair<ll,ll>> edges;
// vector<ll> dist(N,INT_MAX);
// void dijkstra(ll start, ll n)
// {
// 	set<pair<ll,ll>> s;
// 	s.insert(mp(0,start));
// 	while(!s.empty())
// 	{
// 		pii p = *s.begin();
// 		s.erase(s.begin());
// 		for(pii u:adj[p.sc])
// 		{
// 			ll to = u.fr;
// 			ll time = u.sc;
// 			if(dist[to] > dist[p.sc]+time)
// 			{
// 				s.erase({dist[to], to});
// 				dist[to] = dist[p.sc]+time;
// 				s.insert({dist[to], to});
// 			}
// 		}
// 	}
// }

// ll dfs(priority_queue<ll>& pq, vvi& adj, ll start, ll par)
// {
// 	ll sum = 1;
// 	for(auto u:adj[start])
// 	{
// 		if(u != par)
// 		{
// 			ll x = dfs(pq, adj, u, start);
// 			pq.push((adj.size()-x)*x);
// 			sum += x;
// 		}
// 	}
// 	return sum;
// }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////// DSU /////////////////////////////////////////////////////////////////

// void make_set(int v) {
//     parent[v] = v;
//     rank[v] = 0;
// }

// int find_set(int v) {
//     if (v == parent[v])
//         return v;
//     return parent[v] = find_set(parent[v]);
// }

// void union_sets(int a, int b) {
//     a = find_set(a);
//     b = find_set(b);
//     if (a != b) {
//         if (rank[a] < rank[b])
//             swap(a, b);
//         parent[b] = a;
//         if (rank[a] == rank[b])
//             rank[a]++;
//     }
// }

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////// segment tree, (l,r) queries from 0 to r-1, 0 based indexing ///////////////////
// struct segtree{
// 	ll size;
// 	vector<ll> segtree;

// 	void init(ll n)
// 	{
// 		size = 1;
// 		while(size<n)
// 		{
// 			size*=2;
// 		}
// 		segtree.assign(2*size,INT_MAX);
// 	}
// 	void build(vector<ll>& a, ll x, ll lx, ll rx)
// 	{
// 		if(rx-lx == 1)
// 		{
// 			if(lx < a.size())
// 			{
// 				segtree[x] = a[lx];
// 			}
// 			return;
// 		}
// 		ll mid = (lx+rx)/2;
// 		build(a,2*x+1,lx,mid);
// 		build(a,2*x+2,mid,rx);
// 		segtree[x] = min(segtree[2*x+1],segtree[2*x+2]);
// 	}
// 	void build(vector<ll>& a)
// 	{
// 		build(a,0,0,size);
// 	}
// 	ll query(ll l, ll r,ll x, ll lx, ll rx)
// 	{
// 		if(r<=lx || l>=rx)
// 			return INT_MAX;
// 		if(r>=rx && l<=lx)
// 			return segtree[x];
// 		ll m = (lx+rx)/2;
// 		ll left = query(l,r,2*x+1,lx,m);
// 		ll right = query(l,r,2*x+2,m,rx);
// 		return min(left,right);

// 	}
// 	ll query(ll l, ll r)
// 	{
// 		return query(l,r,0,0,size);
// 	}
// };
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

ll t, n, m;

void solve()
{
	cin >> n;
	vi a(n), b(n);
	vi va(n, 0);
	map<ll, ll> pos;
	rep(i, 0, n)
	{
		cin >> a[i];
		pos[a[i]] = i;
	}
	rep(i, 0, n)
	{
		cin >> b[i];

	}
	int ans = 0;
	rep(i, 0, n)
	{
		if (va[i] == 0)
		{
			ll j = i;
			while (va[j] == 0)
			{
				va[j] = 1;
				j = pos[b[j]];
			}
			ans = (ans + 1) % mod;
		}
	}
	ll v = powe(2, ans);
	cout << v << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	cin >> t;
	// t = 1;
	while (t--)
	{
		solve();
	}
}
```