#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll v):v(normS(v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll u[]={a,1,0},v[]={b,0,1};
		while(*v){
			ll t=*u/ *v;
			rep(i,3) swap(u[i]-=t*v[i],v[i]);
		}
		if(u[0]<0) rep(i,3) u[i]=-u[i];
		x=u[1],y=u[2];
		return u[0];
	}
	ModInt inv() const{
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<1000000007>;
using P = pair<int,int>;
int N,n;
//a:0 1 2 ..
int A[399],B[399];
int pA[399],pB[399];

void input(){
	cin>>N;
	n = N/3;
	// vector<int> a(N),ia(N);
	// rep(i,N) cin>>a[i],a[i]--,ia[a[i]] = i;
	// rep(i,N){
	// 	cin>>b[i],b[i]--;
	// 	b[i] = ia[b[i]];
	// }
	rep(i,N) cin>>A[i],A[i]--;
	rep(i,N) cin>>B[i],B[i]--;
	rep(i,N) pA[A[i]] = i, pB[B[i]] = i;
}
mint dp[135][401][401];
mint ac[402][402];

bool inA(int x,int a){
	return pA[x]<a;
}
bool inB(int x,int a){
	return pB[x]<a;
}
int var[401][401];

int main(){
	input();
	if(A[0]==B[0]){
		puts("0");
		return 0;
	}

	rep(i,N+1) rep(j,N+1){
		vector<bool> is(401,false);
		rep(k,i) is[A[k]] = 1;
		rep(k,j) is[B[k]] = 1;
		rep(k,N) if(is[k]) var[i][j]++;
	}
	vector<P> maximal;
	rep1(i,N-1) rep1(j,N-1){
		if(var[i][j] < var[i+1][j] && var[i][j] < var[i][j+1]) maximal.pb(P(i,j));
	}

	dp[1][1][1] = 1;
	rep1(i,n-1){
//		printf("-----i=%d--------\n",i);
		rep(j,N+2) rep(k,N+2) ac[j][k] = 0;
		rep(j,N+1) rep(k,N+1) ac[j+1][k+1] = dp[i][j][k];
		rep(j,N+1) rep(k,N+2) ac[j+1][k] += ac[j][k];
		rep(j,N+2) rep(k,N+1) ac[j][k+1] += ac[j][k];

		for(P p:maximal){
			int x = p.fs, y = p.sc;
			if(A[x]==B[y]) continue;

			int coef = i+1 - (var[x][y]-2*i);
			if(coef<=0) continue;

			dp[i+1][x+1][y+1] += ac[x+1][y+1] * coef;
//			printf("dp[%d][%d][%d] += %d * %d\n",i+1,x+1,y+1,ac[x+1][y+1].v,coef);
		}
	}
	mint ans = 0;
	rep(j,N+1) rep(k,N+1) ans += dp[n][j][k];
	rep1(i,N) if(i%3) ans *= i;
	cout<<ans<<endl;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

Three men, A, B and C, are eating sushi together. Initially, there are N pieces of sushi, numbered 1 through N. Here, N is a multiple of 3.

Each of the three has likes and dislikes in sushi. A's preference is represented by (a_1,\ ...,\ a_N), a permutation of integers from 1 to N. For each i (1 \leq i \leq N), A's i-th favorite sushi is Sushi a_i. Similarly, B's and C's preferences are represented by (b_1,\ ...,\ b_N) and (c_1,\ ...,\ c_N), permutations of integers from 1 to N.

The three repeats the following action until all pieces of sushi are consumed or a fight brakes out (described later):

* Each of the three A, B and C finds his most favorite piece of sushi among the remaining pieces. Let these pieces be Sushi x, y and z, respectively. If x, y and z are all different, A, B and C eats Sushi x, y and z, respectively. Otherwise, a fight brakes out.



You are given A's and B's preferences, (a_1,\ ...,\ a_N) and (b_1,\ ...,\ b_N). How many preferences of C, (c_1,\ ...,\ c_N), leads to all the pieces of sushi being consumed without a fight? Find the count modulo 10^9+7.

Constraints

* 3 \leq N \leq 399
* N is a multiple of 3.
* (a_1,\ ...,\ a_N) and (b_1,\ ...,\ b_N) are permutations of integers from 1 to N.

Input

Input is given from Standard Input in the following format:


N
a_1 ... a_N
b_1 ... b_N


Output

Print the number of the preferences of C that leads to all the pieces of sushi being consumed without a fight, modulo 10^9+7.

Examples

Input

3
1 2 3
2 3 1


Output

2


Input

3
1 2 3
1 2 3


Output

0


Input

6
1 2 3 4 5 6
2 1 4 3 6 5


Output

80


Input

6
1 2 3 4 5 6
6 5 4 3 2 1


Output

160


Input

9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6


Output

33600

### Response

```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll v):v(normS(v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll u[]={a,1,0},v[]={b,0,1};
		while(*v){
			ll t=*u/ *v;
			rep(i,3) swap(u[i]-=t*v[i],v[i]);
		}
		if(u[0]<0) rep(i,3) u[i]=-u[i];
		x=u[1],y=u[2];
		return u[0];
	}
	ModInt inv() const{
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<1000000007>;
using P = pair<int,int>;
int N,n;
//a:0 1 2 ..
int A[399],B[399];
int pA[399],pB[399];

void input(){
	cin>>N;
	n = N/3;
	// vector<int> a(N),ia(N);
	// rep(i,N) cin>>a[i],a[i]--,ia[a[i]] = i;
	// rep(i,N){
	// 	cin>>b[i],b[i]--;
	// 	b[i] = ia[b[i]];
	// }
	rep(i,N) cin>>A[i],A[i]--;
	rep(i,N) cin>>B[i],B[i]--;
	rep(i,N) pA[A[i]] = i, pB[B[i]] = i;
}
mint dp[135][401][401];
mint ac[402][402];

bool inA(int x,int a){
	return pA[x]<a;
}
bool inB(int x,int a){
	return pB[x]<a;
}
int var[401][401];

int main(){
	input();
	if(A[0]==B[0]){
		puts("0");
		return 0;
	}

	rep(i,N+1) rep(j,N+1){
		vector<bool> is(401,false);
		rep(k,i) is[A[k]] = 1;
		rep(k,j) is[B[k]] = 1;
		rep(k,N) if(is[k]) var[i][j]++;
	}
	vector<P> maximal;
	rep1(i,N-1) rep1(j,N-1){
		if(var[i][j] < var[i+1][j] && var[i][j] < var[i][j+1]) maximal.pb(P(i,j));
	}

	dp[1][1][1] = 1;
	rep1(i,n-1){
//		printf("-----i=%d--------\n",i);
		rep(j,N+2) rep(k,N+2) ac[j][k] = 0;
		rep(j,N+1) rep(k,N+1) ac[j+1][k+1] = dp[i][j][k];
		rep(j,N+1) rep(k,N+2) ac[j+1][k] += ac[j][k];
		rep(j,N+2) rep(k,N+1) ac[j][k+1] += ac[j][k];

		for(P p:maximal){
			int x = p.fs, y = p.sc;
			if(A[x]==B[y]) continue;

			int coef = i+1 - (var[x][y]-2*i);
			if(coef<=0) continue;

			dp[i+1][x+1][y+1] += ac[x+1][y+1] * coef;
//			printf("dp[%d][%d][%d] += %d * %d\n",i+1,x+1,y+1,ac[x+1][y+1].v,coef);
		}
	}
	mint ans = 0;
	rep(j,N+1) rep(k,N+1) ans += dp[n][j][k];
	rep1(i,N) if(i%3) ans *= i;
	cout<<ans<<endl;
}

```