#include<bits/stdc++.h>
using namespace std;



#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 pii               pair<ll,ll>
#define piii              pair<pair<ll,ll>,ll>
#define Piii              pair<ll,pair<ll,ll>>
#define p_queue(a)        priority_queue<a, vector<a>, greater<a>>
#define mp                make_pair
#define se                second
#define fi                first
#define vi(a)             vector<a>
#define vvi(a)            vector <vector <a> >
#define pie               3.14159265358979323846
#define for0(i,a,b)       for(ll i=a;i<b;i++)
#define for1(i,a,b)       for(ll i=a;i<=b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define sum(a)     		  ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)           (*min_element((a).begin(), (a).end()))
#define maxe(a)           (*max_element((a).begin(), (a).end()))
#define mini(a)           ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)           ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x)        ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x)        ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

//#define nsetbits(x)        __builtin_popcountll(x)


//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp> 
//using namespace __gnu_pbds; 
// 
//template <typename num_t>
//using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//auto dist=uniform_int_distribution<ll>(l,r);

//typedef ll ll;
typedef long long ll;

const ll inf = 1000000007;
const ll mod = 1000000007;
const ll MOD = 998244353;
const ll INF = 1e18 + 18;


vector<ll> dx={-1LL, 0LL, 1LL, 0LL}, dy={0LL, 1LL, 0LL, -1LL};
//vector<ll> dx={-1, -1, 0, 1, 1, 1, 0, -1}, dy={0, 1, 1, 1, 0, -1, -1, -1};


//string vowels = "aeiou";
//string consonants = "bcdfghjklmnpqrstvwxyz";
//string numbers = "0123456789";
//string alpha = "abcdefghijklmnopqrstuvwxyz";









void test_case(){
	
	
	ll n;
	cin>>n;
	vector<vector<ll>> arr(2,vector<ll>(n+1));
	vector<vector<ll>> pos(2,vector<ll>(n+1));
	for(ll i=0;i<2;i++){
		for(ll j=1;j<=n;j++){
			cin>>arr[i][j];
			pos[i][arr[i][j]] = j;
		}
	}
	vector<bool> vis(n+1,false);
	ll cnt = 0;
	for(ll i=1;i<=n;i++){
		if(vis[i] == true){
			continue;
		}
		vis[i] = true;
		ll j = pos[0][i];
		ll val = arr[1][j];
		while(!vis[val]){
			vis[val] = true;
			j = pos[0][val];
			val = arr[1][j];
		}
		cnt += 1;
	}
	ll ans = 1;
	for(ll i=1;i<=cnt;i++){
		ans = (ans*2)%mod;
	}
	cout<<ans<<endl;
	


}



void intialize(){

	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);

}

void preprocess(){
	
	
	
	
}

void codejam(ll t){
	cout<<"Case #"<<t<<": ";
}

int main(){
//	clock_t start,end;
//	start = clock();
   	intialize();
   	preprocess();
   	cout<<fixed<<setprecision(16);
//	string a;
//	getline(cin,a);
//   	test_case();
	ll t;
	cin>>t;
	for(ll te=1;te<=t;te++){
//		codejam(te);
		test_case();
	}
//	end = clock();
//	double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
//    cout << "Time taken by program is : " << fixed << time_taken << setprecision(10);
//    cout << " sec " << endl;


	return 0;
}

/*

to_string() ---> converts number to string;

stoi()   ------> converts string to number;

substr(i,l)  -----> gives substring starting from index 'i' of len 'l';

__builtin_popcountll(x)   -----> gives no.of setbits in x;

order_of_key: The number of items in a set that are strictly smaller than k

find_by_order: It returns an iterator to the ith largest element

ll f = upper_bound(all(g[x]),r) - lower_bound(all(g[x]),l);
it gives the frequency of element x in the range [L,R]

*/


### 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 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 pii               pair<ll,ll>
#define piii              pair<pair<ll,ll>,ll>
#define Piii              pair<ll,pair<ll,ll>>
#define p_queue(a)        priority_queue<a, vector<a>, greater<a>>
#define mp                make_pair
#define se                second
#define fi                first
#define vi(a)             vector<a>
#define vvi(a)            vector <vector <a> >
#define pie               3.14159265358979323846
#define for0(i,a,b)       for(ll i=a;i<b;i++)
#define for1(i,a,b)       for(ll i=a;i<=b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define sum(a)     		  ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)           (*min_element((a).begin(), (a).end()))
#define maxe(a)           (*max_element((a).begin(), (a).end()))
#define mini(a)           ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)           ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x)        ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x)        ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

//#define nsetbits(x)        __builtin_popcountll(x)


//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp> 
//using namespace __gnu_pbds; 
// 
//template <typename num_t>
//using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//auto dist=uniform_int_distribution<ll>(l,r);

//typedef ll ll;
typedef long long ll;

const ll inf = 1000000007;
const ll mod = 1000000007;
const ll MOD = 998244353;
const ll INF = 1e18 + 18;


vector<ll> dx={-1LL, 0LL, 1LL, 0LL}, dy={0LL, 1LL, 0LL, -1LL};
//vector<ll> dx={-1, -1, 0, 1, 1, 1, 0, -1}, dy={0, 1, 1, 1, 0, -1, -1, -1};


//string vowels = "aeiou";
//string consonants = "bcdfghjklmnpqrstvwxyz";
//string numbers = "0123456789";
//string alpha = "abcdefghijklmnopqrstuvwxyz";









void test_case(){
	
	
	ll n;
	cin>>n;
	vector<vector<ll>> arr(2,vector<ll>(n+1));
	vector<vector<ll>> pos(2,vector<ll>(n+1));
	for(ll i=0;i<2;i++){
		for(ll j=1;j<=n;j++){
			cin>>arr[i][j];
			pos[i][arr[i][j]] = j;
		}
	}
	vector<bool> vis(n+1,false);
	ll cnt = 0;
	for(ll i=1;i<=n;i++){
		if(vis[i] == true){
			continue;
		}
		vis[i] = true;
		ll j = pos[0][i];
		ll val = arr[1][j];
		while(!vis[val]){
			vis[val] = true;
			j = pos[0][val];
			val = arr[1][j];
		}
		cnt += 1;
	}
	ll ans = 1;
	for(ll i=1;i<=cnt;i++){
		ans = (ans*2)%mod;
	}
	cout<<ans<<endl;
	


}



void intialize(){

	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);

}

void preprocess(){
	
	
	
	
}

void codejam(ll t){
	cout<<"Case #"<<t<<": ";
}

int main(){
//	clock_t start,end;
//	start = clock();
   	intialize();
   	preprocess();
   	cout<<fixed<<setprecision(16);
//	string a;
//	getline(cin,a);
//   	test_case();
	ll t;
	cin>>t;
	for(ll te=1;te<=t;te++){
//		codejam(te);
		test_case();
	}
//	end = clock();
//	double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
//    cout << "Time taken by program is : " << fixed << time_taken << setprecision(10);
//    cout << " sec " << endl;


	return 0;
}

/*

to_string() ---> converts number to string;

stoi()   ------> converts string to number;

substr(i,l)  -----> gives substring starting from index 'i' of len 'l';

__builtin_popcountll(x)   -----> gives no.of setbits in x;

order_of_key: The number of items in a set that are strictly smaller than k

find_by_order: It returns an iterator to the ith largest element

ll f = upper_bound(all(g[x]),r) - lower_bound(all(g[x]),l);
it gives the frequency of element x in the range [L,R]

*/


```