Language: C++

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int mod=1e9+7;
const int N=410,maxn=400;
int c[N][N],cj[N];
int dp[N][N][N];
int next[N][N][2];
int ans;
int vis[N];
int a[N],b[N];
int kind[N][N];
int n;

void init(){
	register int i,j;int now;
	next[0][0][0]=1;
	next[0][0][1]=1;
	rep(i,0,n){
		rep(j,1,n)	vis[j]=0;
		rep(j,1,i)	vis[a[j]]=1;
		now=i;
		next[i][0][0]=i+1;
		next[i][0][1]=1;
		while(vis[b[next[i][0][1]]])	next[i][0][1]++;
		rep(j,1,n){
			if(vis[b[j]]==0)	now++;
			vis[b[j]]=1;
			kind[i][j]=now;
			next[i][j][0]=next[i][j-1][0];
			next[i][j][1]=next[i][j-1][1];
			while(vis[a[next[i][j][0]]])	next[i][j][0]++;
			while(vis[b[next[i][j][1]]])	next[i][j][1]++;
		}
	}
	rep(i,0,n)	for(j=1,c[i][0]=1;j<=i;j++)	c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	for(cj[0]=1,i=1;i<=n;i++)	cj[i]=1ll*cj[i-1]*i%mod;
	/*rep(i,0,n){
		rep(j,0,n){
			//printf("next[%d][%d]=%d %d\n",i,j,next[i][j][0],next[i][j][1]);
			printf("kind[%d][%d]=%d\n",i,j,kind[i][j]);
		}
	}*/
}			

int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	register int i,j,k,ni,nj,x;
	scanf("%d",&n);
	rep(i,1,n)	scanf("%d",&a[i]);
	rep(i,1,n)	scanf("%d",&b[i]);
	a[n+1]=n+1;b[n+1]=n+2;
	init();
	dp[0][0][0]=1;
	rep(k,1,n/3){
		rep(i,k-1,n)	rep(j,k-1,n)	if(dp[k-1][i][j]){
			ni=next[i][j][0];nj=next[i][j][1];//cerr<<i<<' '<<j<<' '<<ni<<' '<<nj<<endl;
			dp[k][ni][nj]=(dp[k][ni][nj]+dp[k-1][i][j])%mod;
		}
		rep(i,k,n)	rep(j,k,n)	if(dp[k][i][j]){
			ni=next[i][j-1][0];nj=a[i]==b[j]?next[i][j][1]:j;
			x=kind[i-1][j-1]-2*(k-1);
			if(k-1-x>0)	dp[k][ni][nj]=(dp[k][ni][nj]+1ll*dp[k][i][j]*(k-1-x))%mod;
		}
		rep(i,k,n)	rep(j,k,n)	if(dp[k][i][j]){
			if(a[i]==b[j])	continue;
			nj=next[i-1][j][1];
			x=kind[i-1][j-1]-2*(k-1);
			if(k-1-x>0) dp[k][i][nj]=(dp[k][i][nj]+1ll*dp[k][i][j]*(k-1-x))%mod;
		}
		rep(i,k,n)	rep(j,k,n)	if(a[i]==b[j])	dp[k][i][j]=0;
		/*rep(i,1,n){
			rep(j,1,n){
				printf("dp[%d][%d][%d]=%d\n",k,i,j,dp[k][i][j]);
			}
		}*/
	}
	rep(i,1,n)	rep(j,1,n)	if(dp[n/3][i][j]){
		x=n-kind[i][j];
		ans=(ans+1ll*dp[n/3][i][j]*cj[x])%mod;
	}
	//cerr<<ans<<endl;
	rep(i,1,n/3)	ans=1ll*ans*c[n-3*(i-1)-1][2]*2%mod;
	printf("%d",ans);
}
	
	
				
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

Compiler output:
a.cc: In function 'void init()':
a.cc:19:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   19 |         register int i,j;int now;
      |                      ^
a.cc:19:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   19 |         register int i,j;int now;
      |                        ^
a.cc:20:9: error: reference to 'next' is ambiguous
   20 |         next[0][0][0]=1;
      |         ^~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:66,
                 from /usr/include/c++/14/algorithm:60,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:21:9: error: reference to 'next' is ambiguous
   21 |         next[0][0][1]=1;
      |         ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:26:17: error: reference to 'next' is ambiguous
   26 |                 next[i][0][0]=i+1;
      |                 ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:27:17: error: reference to 'next' is ambiguous
   27 |                 next[i][0][1]=1;
      |                 ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:28:29: error: reference to 'next' is ambiguous
   28 |                 while(vis[b[next[i][0][1]]])    next[i][0][1]++;
      |                             ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:28:49: error: reference to 'next' is ambiguous
   28 |                 while(vis[b[next[i][0][1]]])    next[i][0][1]++;
      |                                                 ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:33:25: error: reference to 'next' is ambiguous
   33 |                         next[i][j][0]=next[i][j-1][0];
      |                         ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:33:39: error: reference to 'next' is ambiguous
   33 |                         next[i][j][0]=next[i][j-1][0];
      |                                       ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:34:25: error: reference to 'next' is ambiguous
   34 |                         next[i][j][1]=next[i][j-1][1];
      |                         ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:34:39: error: reference to 'next' is ambiguous
   34 |                         next[i][j][1]=next[i][j-1][1];
      |                                       ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:35:37: error: reference to 'next' is ambiguous
   35 |                         while(vis[a[next[i][j][0]]])    next[i][j][0]++;
      |                                     ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:35:57: error: reference to 'next' is ambiguous
   35 |                         while(vis[a[next[i][j][0]]])    next[i][j][0]++;
      |                                                         ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:36:37: error: reference to 'next' is ambiguous
   36 |                         while(vis[b[next[i][j][1]]])    next[i][j][1]++;
      |                                     ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:36:57: error: reference to 'next' is ambiguous
   36 |                         while(vis[b[next[i][j][1]]])    next[i][j][1]++;
      |                                                         ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc: In function 'int main()':
a.cc:52:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |         register int i,j,k,ni,nj,x;
      |                      ^
a.cc:52:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |         register int i,j,k,ni,nj,x;
      |                        ^
a.cc:52:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |         register int i,j,k,ni,nj,x;
      |                          ^
a.cc:52:28: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |         register int i,j,k,ni,nj,x;
      |                            ^~
a.cc:52:31: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |         register int i,j,k,ni,nj,x;
      |                               ^~
a.cc:52:34: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |         register int i,j,k,ni,nj,x;
      |                                  ^
a.cc:61:28: error: reference to 'next' is ambiguous
   61 |                         ni=next[i][j][0];nj=next[i][j][1];//cerr<<i<<' '<<j<<' '<<ni<<' '<<nj<<endl;
      |                            ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [410][410][2]'
   11 | int next[N][N][2];
      |     ^~~~
a.cc:61:45: error: reference to 'next' is ambiguous
   61 |                         ni=next[i][j][0];nj=next[i][j][1];//cerr<<i<<' '<<j<<' '<<ni<<' '<<nj<<endl;
      |                                             ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:11:5: note:                 'int next [41