//ANIKET'S SOLUTION XD
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
#define MOD 1000000007
//ull MOD = 1000000007;
#define single solve(0);
#define testCases int t; cin>>t; for(int z1=1; z1<=t; z1++){ solve(z1);}
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define lld long double
#define ull unsigned long long
#define endl '\n'
#define root2 1.41421
#define root3 1.73205
#define cntbit __builtin_popcountll
#define sz(s) s.size()
#define INF 10000000000000000
#define mp make_pair
#define vi vector<int>
#define ss second
#define pb push_back
#define ff first
#define pii pair<int,int>
#define vii vector<pii>
#define pq priority_queue<int>
#define pdq priority_queue<int, vi, greater<int> >
#define prl(x) {cout<<x<<endl;}
#define printArr(arr,st,en) for(int i=st;i<=en;i++)cout<<arr[i]<<" "; cout<<endl;
#define gcd __gcd
double pi = 3.141592653589793238;


using namespace std;

//namespace number_theory {
//
//bool prime[15000105];
//void sieve(int n) {
//    for (ll i = 0; i <= n; i++) prime[i] = 1;
//    for (ll p = 2; p * p <= n; p++) {
//        if (prime[p] == true) {
//            for (ll i = p * p; i <= n; i += p)
//            prime[i] = false;
//        }
//    }
//    prime[1] = prime[0] = 0;
//}
//
//vector<ll> primelist;
//bool _primes_generated_ = 0;
//
//void genprimes(int n) {
//    _primes_generated_ = 1;
//    sieve(n + 1);
//    for (ll i = 2; i <= n; i++) if (prime[i]) primelist.push_back(i);
//}
//
//vector<ll> factors(ll n) {
//    if (!_primes_generated_) {
//        cerr << "Call genprimes you dope" << endl;
//        exit(1);
//    }
//    vector<ll> facs;
//
//    for (ll i = 0; primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {
//        if (n % primelist[i] == 0) {
//            while (n % primelist[i] == 0) {
//                n /= primelist[i];
//                facs.push_back(primelist[i]);
//            }
//        }
//    }
//    if (n > 1) {
//        facs.push_back(n);
//    }
//    // sort(all(facs));
//    return facs;
//}
//}

//using namespace number_theory;

int __gcd(int a,int b){
    if(b==0)
        return a;
    if(b>a)
        return __gcd(b,a);
    return __gcd(b,a%b);
}



int power(int x, unsigned int y){
    int res = 1;
    x = x%MOD;
    if(x==0) return 0;

    while(y>0){
        if(y&1) res = ((res*x)%MOD+MOD)%MOD;
        y = y>>1;
        x = ((x*x)%MOD+MOD)%MOD;
    }
    return res%MOD;
}

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

bool checkPrime(int n){

    //    int root = sqrt(n);
    int count = 0;
    for(int i=1;(i*i)<=n;i++){
        //        if(i%2)
        //            continue;
        if((i*i)==n){
            count++;
            continue;
        }
        if(n%i==0)
            count+=2;

    }


    if(count==2)
        return true;

    return false;

}

int lcm(int a, int b){
    return a*b/(gcd(a, b));
}




using namespace std;


//int query(int *arr, int* tree, int start, int end, int treeNode,int left,int right){
////    if(left==right){
////        return tree[treeNode];
////    }
//
//    if((left>end)||(right<start)){
//        return -1;
//    }
//    if((left>=start)&&(right<=end)){
//        return tree[treeNode];
//    }
//
//    int mid = (left+right)/2;
//
//    int ans1 = query(arr,tree,start,end,treeNode*2+1,left,mid);
//    int ans2 = query(arr,tree,start,end,treeNode*2+2,mid+1,right);
//
//    return max(ans1,ans2);
//}
//
//void update(int *arr, int *tree, int start, int end, int po, int va, int treeNode){
//
//    if(start>po||end<po)
//        return;
//    if(start==end){
//        arr[start] = va;
//        tree[treeNode] = va;
//        return;
//    }
//
//    int mid = (start+end)/2;
//
//    update(arr,tree,start,mid,po,va,treeNode*2+1);
//    update(arr,tree,mid+1,end,po,va,(treeNode*2)+2);
//
//    tree[treeNode] = min(tree[2*treeNode+1] , tree[(treeNode*2) + 2]);
//    return;
//
//}
//
//void buildTree(int *arr, int* tree, int start, int end, int treeNode){
//
//    if(start==end){
//        tree[treeNode] = arr[start];
//        return;
//    }
////    if(start==(end-1)){
////        tree[treeNode] = max(arr[start],arr[end]);
////        return;
////    }
//
//    int mid = (start+end)/2;
//
//    buildTree(arr,tree,start,mid,2*treeNode+1);
//    buildTree(arr,tree,mid+1,end,2*treeNode+2);
//
//    tree[treeNode] = max(tree[treeNode*2+1],tree[treeNode*2+2]);
//}

//int par[1001],level[1001];
//int part(int x){
//    if(par[x]==-1){
//        return x;
//    }
//    return par[x]=part(par[x]);
//}
//void unite(int x,int y){
//    int p1=part(x);
//    int p2=part(y);
//    if(p1 != p2){
//        if(level[p1] > level[p2]){
//            par[p2]=p1;
//            level[p1]+=level[p2];
//        }else{
//            par[p1]=p2;
//            level[p2]+=level[p1];
//        }
//    }
//}
//

// Euler totient function phi(n) => nos(gcd(x, n)) == 1 for all 1<=x<n ie total count of numbers coprime to n
int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

vector<int> prime1;
int N = 2e7+5;
//int fib[200005];
set<int> s;



void primeSieve(){
    bool *arr = new bool[N];

    for(int i=0;i<N;i++)
    arr[i] = true;

    arr[0] = false;
    arr[1] = false;

    //    int root = sqrt(N);

    for(int i=1;i*i<=N;i++){
        if(arr[i]==false)
            continue;
        else{
            for(int j=i*i;j<N;j+=i){
                arr[j] = false;
                //                while((fac[j]%(i*i))==0)
                //                    fac[j] /= i*i;
            }
        }
    }


    for(int i=0;i<N;i++){
        if(arr[i]==true){
            prime1.pb(i);
            s.insert(i);
        }
    }
}

//int factors1[2000005];
//void factors(){
//        for(int i=0;i<2000005;i++){
//            factors1[i] = i;
//        }
//        for(int i=2;i<2000005;i+=2){
//            factors1[i] = 2;
//        }
//        for (int i=3; i*i<2000005; i++) {
//            if (factors1[i] == i) {
//                for (int j=i*i; j<2000005; j+=i)
//                if (factors1[j]==j)
//                    factors1[j] = i;
//            }
//        }
//}

//void fibonacci(){
//    fib[0] = 1;
//    fib[1] = 1;
//    fib[2] = 1;
//    for(int i=3;i<200005;i++){
//        fib[i] = (fib[i-1]+fib[i-2])%MOD;
//    }
//}

//ll fac[1000001] = {1};
//void factorial(){
//    fac[0] = 1;
//    for(ull i=1;i<1000001;i++){
//        fac[i] = (((((fac[i-1])+MOD)%MOD)*i)+MOD)%MOD;
//    }
//}
//
//ll C(ll a,ll b){
//    if(a==0)
//        return 0;
//    if(b>a)
//        return 0;
//    if(b==0||b==a)
//        return 1;
//    int div = ((fac[b]*fac[a-b]))%MOD;
//    div = power(div,MOD-2)%MOD;
//    return (fac[a]*div)%MOD;
//}

int ceil(int a,int b){
    return (a+b-1)/b;
}

bool cmp(pii a, pii b){
    return (a.ff/a.ss)>(b.ff/b.ss);
}

//struct myComparator
//{
//public:
//    bool operator() (const pair<int,pii> &a, const pair<int,pii> &b)
//    {
//        if(a.ff==b.ff){
//            return a.ss.ff>b.ss.ff;
//        }
//        return a.ff<b.ff;
//    }
//};

//int fun(int x,int y){
//    if(y==0)
//        return 0;
//    int ans = INT_MAX;
//    int p = x;
//    while(p<=y){
//        if(p==y){
//            ans = 1;
//        }
//        ans = min(ans,1+fun(x,y-p));
//        p *= 2;
//    }
//    return ans;
//}

//int divCnt[2000005];
//void numOfDiv(){
//    int n = 2000005;
//    for(int i=1;i<n;i++){
//        for(int j=i;j<n;j+=i){
//            divCnt[j]++;
//        }
//    }
//}
map<int,int> m;
set<int> vis;
set<int> visited;
bool fun(int curr,int req){
    if(visited.count(curr))
        return false;
    else visited.insert(curr);
    if(m[curr]==req){
        vis.insert(curr);
        return true;
    }else if(fun(m[curr],req)){
        vis.insert(curr);
        return true;
    }else return false;
}


void solve(int test){
    
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vis.clear();
    int b[n];
    m.clear();
    for(int i=0;i<n;i++){
        cin>>b[i];
        m[a[i]] = b[i];
    }
    int count = 1;
    for(int i=0;i<n;i++){
        if(!vis.count(a[i])){
            visited.clear();
            if(fun(b[i],a[i])){
                count *= 2;
                count %= MOD;
            }
        }
    }
    cout<<count<<"\n";
}
signed main()
{

//            primeSieve();
    //        factors();
//                factorial();
    //    fibonacci()
    //    #ifndef ONLINE_JUDGE
    //        freopen("input.txt","r", stdin);
    //        freopen("output.txt","w",stdout);
    //    #endif
    //    numOfDiv();

    fastIO;
//    single;
    testCases;

    return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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
//ANIKET'S SOLUTION XD
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
#define MOD 1000000007
//ull MOD = 1000000007;
#define single solve(0);
#define testCases int t; cin>>t; for(int z1=1; z1<=t; z1++){ solve(z1);}
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define lld long double
#define ull unsigned long long
#define endl '\n'
#define root2 1.41421
#define root3 1.73205
#define cntbit __builtin_popcountll
#define sz(s) s.size()
#define INF 10000000000000000
#define mp make_pair
#define vi vector<int>
#define ss second
#define pb push_back
#define ff first
#define pii pair<int,int>
#define vii vector<pii>
#define pq priority_queue<int>
#define pdq priority_queue<int, vi, greater<int> >
#define prl(x) {cout<<x<<endl;}
#define printArr(arr,st,en) for(int i=st;i<=en;i++)cout<<arr[i]<<" "; cout<<endl;
#define gcd __gcd
double pi = 3.141592653589793238;


using namespace std;

//namespace number_theory {
//
//bool prime[15000105];
//void sieve(int n) {
//    for (ll i = 0; i <= n; i++) prime[i] = 1;
//    for (ll p = 2; p * p <= n; p++) {
//        if (prime[p] == true) {
//            for (ll i = p * p; i <= n; i += p)
//            prime[i] = false;
//        }
//    }
//    prime[1] = prime[0] = 0;
//}
//
//vector<ll> primelist;
//bool _primes_generated_ = 0;
//
//void genprimes(int n) {
//    _primes_generated_ = 1;
//    sieve(n + 1);
//    for (ll i = 2; i <= n; i++) if (prime[i]) primelist.push_back(i);
//}
//
//vector<ll> factors(ll n) {
//    if (!_primes_generated_) {
//        cerr << "Call genprimes you dope" << endl;
//        exit(1);
//    }
//    vector<ll> facs;
//
//    for (ll i = 0; primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {
//        if (n % primelist[i] == 0) {
//            while (n % primelist[i] == 0) {
//                n /= primelist[i];
//                facs.push_back(primelist[i]);
//            }
//        }
//    }
//    if (n > 1) {
//        facs.push_back(n);
//    }
//    // sort(all(facs));
//    return facs;
//}
//}

//using namespace number_theory;

int __gcd(int a,int b){
    if(b==0)
        return a;
    if(b>a)
        return __gcd(b,a);
    return __gcd(b,a%b);
}



int power(int x, unsigned int y){
    int res = 1;
    x = x%MOD;
    if(x==0) return 0;

    while(y>0){
        if(y&1) res = ((res*x)%MOD+MOD)%MOD;
        y = y>>1;
        x = ((x*x)%MOD+MOD)%MOD;
    }
    return res%MOD;
}

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

bool checkPrime(int n){

    //    int root = sqrt(n);
    int count = 0;
    for(int i=1;(i*i)<=n;i++){
        //        if(i%2)
        //            continue;
        if((i*i)==n){
            count++;
            continue;
        }
        if(n%i==0)
            count+=2;

    }


    if(count==2)
        return true;

    return false;

}

int lcm(int a, int b){
    return a*b/(gcd(a, b));
}




using namespace std;


//int query(int *arr, int* tree, int start, int end, int treeNode,int left,int right){
////    if(left==right){
////        return tree[treeNode];
////    }
//
//    if((left>end)||(right<start)){
//        return -1;
//    }
//    if((left>=start)&&(right<=end)){
//        return tree[treeNode];
//    }
//
//    int mid = (left+right)/2;
//
//    int ans1 = query(arr,tree,start,end,treeNode*2+1,left,mid);
//    int ans2 = query(arr,tree,start,end,treeNode*2+2,mid+1,right);
//
//    return max(ans1,ans2);
//}
//
//void update(int *arr, int *tree, int start, int end, int po, int va, int treeNode){
//
//    if(start>po||end<po)
//        return;
//    if(start==end){
//        arr[start] = va;
//        tree[treeNode] = va;
//        return;
//    }
//
//    int mid = (start+end)/2;
//
//    update(arr,tree,start,mid,po,va,treeNode*2+1);
//    update(arr,tree,mid+1,end,po,va,(treeNode*2)+2);
//
//    tree[treeNode] = min(tree[2*treeNode+1] , tree[(treeNode*2) + 2]);
//    return;
//
//}
//
//void buildTree(int *arr, int* tree, int start, int end, int treeNode){
//
//    if(start==end){
//        tree[treeNode] = arr[start];
//        return;
//    }
////    if(start==(end-1)){
////        tree[treeNode] = max(arr[start],arr[end]);
////        return;
////    }
//
//    int mid = (start+end)/2;
//
//    buildTree(arr,tree,start,mid,2*treeNode+1);
//    buildTree(arr,tree,mid+1,end,2*treeNode+2);
//
//    tree[treeNode] = max(tree[treeNode*2+1],tree[treeNode*2+2]);
//}

//int par[1001],level[1001];
//int part(int x){
//    if(par[x]==-1){
//        return x;
//    }
//    return par[x]=part(par[x]);
//}
//void unite(int x,int y){
//    int p1=part(x);
//    int p2=part(y);
//    if(p1 != p2){
//        if(level[p1] > level[p2]){
//            par[p2]=p1;
//            level[p1]+=level[p2];
//        }else{
//            par[p1]=p2;
//            level[p2]+=level[p1];
//        }
//    }
//}
//

// Euler totient function phi(n) => nos(gcd(x, n)) == 1 for all 1<=x<n ie total count of numbers coprime to n
int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

vector<int> prime1;
int N = 2e7+5;
//int fib[200005];
set<int> s;



void primeSieve(){
    bool *arr = new bool[N];

    for(int i=0;i<N;i++)
    arr[i] = true;

    arr[0] = false;
    arr[1] = false;

    //    int root = sqrt(N);

    for(int i=1;i*i<=N;i++){
        if(arr[i]==false)
            continue;
        else{
            for(int j=i*i;j<N;j+=i){
                arr[j] = false;
                //                while((fac[j]%(i*i))==0)
                //                    fac[j] /= i*i;
            }
        }
    }


    for(int i=0;i<N;i++){
        if(arr[i]==true){
            prime1.pb(i);
            s.insert(i);
        }
    }
}

//int factors1[2000005];
//void factors(){
//        for(int i=0;i<2000005;i++){
//            factors1[i] = i;
//        }
//        for(int i=2;i<2000005;i+=2){
//            factors1[i] = 2;
//        }
//        for (int i=3; i*i<2000005; i++) {
//            if (factors1[i] == i) {
//                for (int j=i*i; j<2000005; j+=i)
//                if (factors1[j]==j)
//                    factors1[j] = i;
//            }
//        }
//}

//void fibonacci(){
//    fib[0] = 1;
//    fib[1] = 1;
//    fib[2] = 1;
//    for(int i=3;i<200005;i++){
//        fib[i] = (fib[i-1]+fib[i-2])%MOD;
//    }
//}

//ll fac[1000001] = {1};
//void factorial(){
//    fac[0] = 1;
//    for(ull i=1;i<1000001;i++){
//        fac[i] = (((((fac[i-1])+MOD)%MOD)*i)+MOD)%MOD;
//    }
//}
//
//ll C(ll a,ll b){
//    if(a==0)
//        return 0;
//    if(b>a)
//        return 0;
//    if(b==0||b==a)
//        return 1;
//    int div = ((fac[b]*fac[a-b]))%MOD;
//    div = power(div,MOD-2)%MOD;
//    return (fac[a]*div)%MOD;
//}

int ceil(int a,int b){
    return (a+b-1)/b;
}

bool cmp(pii a, pii b){
    return (a.ff/a.ss)>(b.ff/b.ss);
}

//struct myComparator
//{
//public:
//    bool operator() (const pair<int,pii> &a, const pair<int,pii> &b)
//    {
//        if(a.ff==b.ff){
//            return a.ss.ff>b.ss.ff;
//        }
//        return a.ff<b.ff;
//    }
//};

//int fun(int x,int y){
//    if(y==0)
//        return 0;
//    int ans = INT_MAX;
//    int p = x;
//    while(p<=y){
//        if(p==y){
//            ans = 1;
//        }
//        ans = min(ans,1+fun(x,y-p));
//        p *= 2;
//    }
//    return ans;
//}

//int divCnt[2000005];
//void numOfDiv(){
//    int n = 2000005;
//    for(int i=1;i<n;i++){
//        for(int j=i;j<n;j+=i){
//            divCnt[j]++;
//        }
//    }
//}
map<int,int> m;
set<int> vis;
set<int> visited;
bool fun(int curr,int req){
    if(visited.count(curr))
        return false;
    else visited.insert(curr);
    if(m[curr]==req){
        vis.insert(curr);
        return true;
    }else if(fun(m[curr],req)){
        vis.insert(curr);
        return true;
    }else return false;
}


void solve(int test){
    
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vis.clear();
    int b[n];
    m.clear();
    for(int i=0;i<n;i++){
        cin>>b[i];
        m[a[i]] = b[i];
    }
    int count = 1;
    for(int i=0;i<n;i++){
        if(!vis.count(a[i])){
            visited.clear();
            if(fun(b[i],a[i])){
                count *= 2;
                count %= MOD;
            }
        }
    }
    cout<<count<<"\n";
}
signed main()
{

//            primeSieve();
    //        factors();
//                factorial();
    //    fibonacci()
    //    #ifndef ONLINE_JUDGE
    //        freopen("input.txt","r", stdin);
    //        freopen("output.txt","w",stdout);
    //    #endif
    //    numOfDiv();

    fastIO;
//    single;
    testCases;

    return 0;
}

```