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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > 
#define pii pair<int,int> 
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define SZ(x) ((int)x.size())
using namespace std;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
const int BufferSize=1<<16;
char buffer[BufferSize],*Bufferhead,*Buffertail;
bool Terminal;
inline char Getchar(){
	if(Bufferhead==Buffertail){
		int l=fread(buffer,1,BufferSize,stdin);
		if(!l){Terminal=1;return 0;}
		Buffertail=(Bufferhead=buffer)+l;
	}
	return *Bufferhead++;
}
template<class T>inline bool read(T &x){
	x=0;char c=Getchar(),rev=0;
	while(c<'0'||c>'9'){rev|=c=='-';c=Getchar();if(Terminal)return 0;}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
	if(c=='.'){
		c=Getchar();double t=0.1;
		while(c>='0'&&c<='9') x=x+(c-'0')*t,c=Getchar(),t=t/10;
	}
	x=rev?-x:x;
	return 1;
}
template<class T1,class T2> inline bool read(T1 &x,T2 &y){return read(x)&read(y);}
template<class T1,class T2,class T3> inline bool read(T1 &x,T2 &y,T3 &z){return read(x)&read(y)&read(z);}
template<class T1,class T2,class T3,class T4> inline bool read(T1 &x,T2 &y,T3 &z,T4 &w){return read(x)&read(y)&read(z)&read(w);}
inline bool reads(char *x){
	char c=Getchar();
	while(c<33||c>126){c=Getchar();if(Terminal)return 0;}
	while(c>=33&&c<=126) (*x++)=c,c=Getchar();
	*x=0;return 1;
}
template<class T>inline void print(T x,const char c='\n'){
	if(!x){putchar('0');putchar(c);return;}
	if(x<0) putchar('-'),x=-x;
	int m=0,a[20];
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');
	putchar(c);
}
//--------------------------------head---------------------------------------------

const int inf=0x3f3f3f3f;
const int N=405,M=100005,mod=1e9+7;
template<class T,class S> inline void ch(T &x,const S y){x=(x+y)%mod;}
inline int exp(int x,int y,const int mod=::mod){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

int n,a[N],b[N],pa[N],pb[N],s[N][N],fac[N],ifac[N];
int dp[N/3][N][N],f[N/3][N],g[N][N];

inline int P(int x,int y){
	if(x<0||y<0||x<y) return 0;
	return (ll)fac[x]*ifac[x-y]%mod;
}
inline bool check(int x,int y){
	if(!x&&!y) return 1;
	return pb[a[x]]>y&&pa[b[y]]>x;
}

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	read(n);
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
	ifac[n]=exp(fac[n],mod-2);
	for(int i=n;i;i--) ifac[i-1]=(ll)ifac[i]*i%mod;
	for(int i=1;i<=n;i++)
		read(a[i]),pa[a[i]]=i;
	for(int i=1;i<=n;i++)
		read(b[i]),pb[b[i]]=i;
	for(int i=0;i<=n;i++){
		s[i][0]=i;
		for(int j=1;j<=n;j++)
			s[i][j]=s[i][j-1]+(pa[b[j]]>i);
	}
	int a1=0,a2=0;
	
	dp[0][0][0]=1;
	for(int i=0;i<n/3;i++){
		for(int x=0;x<=n;x++)
			for(int y=0;y<=n;y++)
				g[x][y]=dp[i][x][y];
		for(int x=0;x<=n;x++)
			for(int y=0;y<=n;y++)
				ch(g[x+1][y],(ll)g[x][y]*P(i*3-s[x][y],s[x+1][y]-s[x][y]));
		for(int x=0;x<=n;x++)
			for(int y=0;y<=n;y++)
				ch(g[x][y+1],(ll)g[x][y]*P(i*3-s[x][y],s[x][y+1]-s[x][y]));
		for(int x=1;x<=n;x++)
			for(int y=1;y<=n;y++)
				dp[i+1][x][y]=check(x,y)?g[x-1][y-1]:0;
	}
	for(int x=1;x<=n;x++)
		for(int y=1;y<=n;y++)
			ch(a1,(ll)dp[n/3][x][y]*fac[n-s[x][y]]);
	f[0][0]=1;
	for(int i=0;i<n/3;i++)
		for(int z=0;z<=n;z++){
			if(!f[i][z]) continue;
			for(int zp=z+1;zp<=n;zp++)
				ch(f[i+1][zp],(ll)f[i][z]*P(i*3-z,zp-z-1));
		}
	for(int z=1;z<=n;z++)
		ch(a2,(ll)f[n/3][z]*fac[n-z]);
	
	print((ll)a1*a2%mod);
	return 0;
}