/*{{{*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
typedef pair<int, int> PP;
typedef long long LL;
#define pb push_back
#define fr first
#define sc second
#define bitcnt __builtin_popcount
#define all(x) x.begin(), x.end()
inline LL ri() {LL x; scanf("%lld", &x); return x;}
#define rep2(i, n, ...) for (int i = 0; i < (n); i ++) 
#define rep3(i, a, b, ...) for (int i = (a); i < (b); i ++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define drep2(i, n, ...) for (int i = (n) - 1; i >= 0; i --)
#define drep3(i, a, b) for (int i = (a) - 1; i >= (b); i --)
#define drep(...) GET_MACRO(__VA_ARGS__, drep3, drep2)(__VA_ARGS__)
template<typename T>inline bool smax(T&a, T b){if(a<b){a=b;return true;}return false;} 
template<typename T>inline bool smin(T&a, T b){if(a>b){a=b;return true;}return false;} 
/*}}}*/

//mod int
struct mint{
  const static long long mod = 1e9 + 7;
  int x;
  mint():x(0){}       
  mint(long long x):x(((x%mod)+mod)%mod){};
  mint operator+=(const mint&a){if((x+=a.x)>=mod) x-=mod; return *this;}
  mint operator-=(const mint&a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint operator*=(const mint&a){x=((LL)x*a.x)%mod; return *this;}
  mint operator*(const mint&a){return mint(*this)*=a;}
  mint operator-(const mint&a){return mint(*this)-=a;}
  mint operator+(const mint&a){return mint(*this)+=a;}
  template<typename T>mint operator*(const T&a){return mint(*this)*=a;}
  template<typename T>mint operator-(const T&a){return mint(*this)-=a;}
  template<typename T>mint operator+(const T&a){return mint(*this)+=a;}
  template<typename T>friend mint operator*(T x,const mint&m){return mint(x)*=m;}
  template<typename T>friend mint operator-(T x,const mint&m){return mint(x)-=m;}
  template<typename T>friend mint operator+(T x,const mint&m){return mint(x)+=m;}
  bool operator==(const mint& a)const{ return x == a.x;}
  operator long long () const {return x;}
};
mint pw(mint a, long long b){mint res(1);while(b){if(b&1)res*=a;a*=a;b>>=1;}return res;}
mint inv(mint a){return pw(a, mint::mod - 2);}
//mod int

int a[405], b[405], pa[405], pb[405], t[405][405], n;

int tx[405][405], ty[405][405];
mint res[405 / 3][405][405][2];

mint& get(int i, int j, int k, int e) {
  int x = tx[j][k];
  int y = ty[j][k];
  //if (x == n || y == n) {
    //cout << i << ' ' << j << ' ' << k << endl;
  //}
  return res[i][x][y][e];
}

int main() {
  cin >> n;
  rep(i, n) cin >> a[i], pa[a[i]] = i;
  rep(i, n) cin >> b[i], pb[b[i]] = i;
  rep(i, n) {
    int s = 0;
    rep(j, n) {
      s += pa[b[j]] <= i;
      t[i + 1][j + 1] = s;
    }
  }
  drep(j, n + 1) drep(k, n + 1) {
    int na = pb[a[j]], nb = pa[b[k]];
    if (j < n && na < k) {
      tx[j][k] = tx[j + 1][k];
      ty[j][k] = ty[j + 1][k];
    } else if (k < n && nb < j) {
      tx[j][k] = tx[j][k + 1];
      ty[j][k] = ty[j][k + 1];
    } else {
      tx[j][k] = j;
      ty[j][k] = k;
    }
  }

  res[0][0][0][0] = 1;
  int m = n / 3;
  rep(i, m + 1) {
    rep(j, i, n) {
      rep(k, i, n) {
        rep(e, 0, 2) {
          if (!res[i][j][k][e]) continue;
          if (tx[j][k] != j || ty[j][k] != k) continue;
          int uniques = j + k - t[j][k];
          int cc = uniques - 2 * i;
          if (cc <= i && cc >= 0) { // valid
              if (a[j] != b[k]) {
                if (i < m) {
                  get(i + 1, j + 1, k + 1, 0) += res[i][j][k][e];
                }
                if (cc < i) {
                  if (e == 0) get(i, j + 1, k, 0) += res[i][j][k][e] * (i - cc);
                  get(i, j, k + 1, 1) += res[i][j][k][e] * (i - cc);
                }
            } else {
              if (cc < i)
                if (e == 0) get(i, j + 1, k + 1, 0)  += res[i][j][k][e] * (i - cc);
            }
          }
        }
      }
    }
  }
  //cout << res[2]
  //cout << res[1][2][1] << endl;
  //cout << res[1][1][1] << endl;
  mint ans = res[m][n][n][0] + res[m][n][n][1];
  //cout << res[2][2][3] << ' ' << endl;
  //cout << res[2][3][2] << ' ' << endl;
  //cout << ans << endl;
  rep(i, m) {
    ans *=  (3 * (m - i) - 1) * (3 * (m - i) - 2);
  }
  cout << ans << endl;
  //cout << res[]
  return 0;
}

### 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 <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
typedef pair<int, int> PP;
typedef long long LL;
#define pb push_back
#define fr first
#define sc second
#define bitcnt __builtin_popcount
#define all(x) x.begin(), x.end()
inline LL ri() {LL x; scanf("%lld", &x); return x;}
#define rep2(i, n, ...) for (int i = 0; i < (n); i ++) 
#define rep3(i, a, b, ...) for (int i = (a); i < (b); i ++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define drep2(i, n, ...) for (int i = (n) - 1; i >= 0; i --)
#define drep3(i, a, b) for (int i = (a) - 1; i >= (b); i --)
#define drep(...) GET_MACRO(__VA_ARGS__, drep3, drep2)(__VA_ARGS__)
template<typename T>inline bool smax(T&a, T b){if(a<b){a=b;return true;}return false;} 
template<typename T>inline bool smin(T&a, T b){if(a>b){a=b;return true;}return false;} 
/*}}}*/

//mod int
struct mint{
  const static long long mod = 1e9 + 7;
  int x;
  mint():x(0){}       
  mint(long long x):x(((x%mod)+mod)%mod){};
  mint operator+=(const mint&a){if((x+=a.x)>=mod) x-=mod; return *this;}
  mint operator-=(const mint&a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint operator*=(const mint&a){x=((LL)x*a.x)%mod; return *this;}
  mint operator*(const mint&a){return mint(*this)*=a;}
  mint operator-(const mint&a){return mint(*this)-=a;}
  mint operator+(const mint&a){return mint(*this)+=a;}
  template<typename T>mint operator*(const T&a){return mint(*this)*=a;}
  template<typename T>mint operator-(const T&a){return mint(*this)-=a;}
  template<typename T>mint operator+(const T&a){return mint(*this)+=a;}
  template<typename T>friend mint operator*(T x,const mint&m){return mint(x)*=m;}
  template<typename T>friend mint operator-(T x,const mint&m){return mint(x)-=m;}
  template<typename T>friend mint operator+(T x,const mint&m){return mint(x)+=m;}
  bool operator==(const mint& a)const{ return x == a.x;}
  operator long long () const {return x;}
};
mint pw(mint a, long long b){mint res(1);while(b){if(b&1)res*=a;a*=a;b>>=1;}return res;}
mint inv(mint a){return pw(a, mint::mod - 2);}
//mod int

int a[405], b[405], pa[405], pb[405], t[405][405], n;

int tx[405][405], ty[405][405];
mint res[405 / 3][405][405][2];

mint& get(int i, int j, int k, int e) {
  int x = tx[j][k];
  int y = ty[j][k];
  //if (x == n || y == n) {
    //cout << i << ' ' << j << ' ' << k << endl;
  //}
  return res[i][x][y][e];
}

int main() {
  cin >> n;
  rep(i, n) cin >> a[i], pa[a[i]] = i;
  rep(i, n) cin >> b[i], pb[b[i]] = i;
  rep(i, n) {
    int s = 0;
    rep(j, n) {
      s += pa[b[j]] <= i;
      t[i + 1][j + 1] = s;
    }
  }
  drep(j, n + 1) drep(k, n + 1) {
    int na = pb[a[j]], nb = pa[b[k]];
    if (j < n && na < k) {
      tx[j][k] = tx[j + 1][k];
      ty[j][k] = ty[j + 1][k];
    } else if (k < n && nb < j) {
      tx[j][k] = tx[j][k + 1];
      ty[j][k] = ty[j][k + 1];
    } else {
      tx[j][k] = j;
      ty[j][k] = k;
    }
  }

  res[0][0][0][0] = 1;
  int m = n / 3;
  rep(i, m + 1) {
    rep(j, i, n) {
      rep(k, i, n) {
        rep(e, 0, 2) {
          if (!res[i][j][k][e]) continue;
          if (tx[j][k] != j || ty[j][k] != k) continue;
          int uniques = j + k - t[j][k];
          int cc = uniques - 2 * i;
          if (cc <= i && cc >= 0) { // valid
              if (a[j] != b[k]) {
                if (i < m) {
                  get(i + 1, j + 1, k + 1, 0) += res[i][j][k][e];
                }
                if (cc < i) {
                  if (e == 0) get(i, j + 1, k, 0) += res[i][j][k][e] * (i - cc);
                  get(i, j, k + 1, 1) += res[i][j][k][e] * (i - cc);
                }
            } else {
              if (cc < i)
                if (e == 0) get(i, j + 1, k + 1, 0)  += res[i][j][k][e] * (i - cc);
            }
          }
        }
      }
    }
  }
  //cout << res[2]
  //cout << res[1][2][1] << endl;
  //cout << res[1][1][1] << endl;
  mint ans = res[m][n][n][0] + res[m][n][n][1];
  //cout << res[2][2][3] << ' ' << endl;
  //cout << res[2][3][2] << ' ' << endl;
  //cout << ans << endl;
  rep(i, m) {
    ans *=  (3 * (m - i) - 1) * (3 * (m - i) - 2);
  }
  cout << ans << endl;
  //cout << res[]
  return 0;
}

```