Problem:


Score : 1800 points

Problem Statement

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.

Sample Input 1

3
1 2 3
2 3 1

Sample Output 1

2

The answer is two, (c_1,\ c_2,\ c_3) = (3,\ 1,\ 2),\ (3,\ 2,\ 1).
In both cases, A, B and C will eat Sushi 1, 2 and 3, respectively, and there will be no more sushi.

Sample Input 2

3
1 2 3
1 2 3

Sample Output 2

0

Regardless of what permutation (c_1,\ c_2,\ c_3) is, A and B will try to eat Sushi 1, resulting in a fight.

Sample Input 3

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

Sample Output 3

80

For example, if (c_1,\ c_2,\ c_3,\ c_4,\ c_5,\ c_6) = (5,\ 1,\ 2,\ 6,\ 3,\ 4), A, B and C will first eat Sushi 1, 2 and 5, respectively, then they will eat Sushi 3, 4 and 6, respectively, and there will be no more sushi.

Sample Input 4

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

Sample Output 4

160

Sample Input 5

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

Sample Output 5

33600



Sample input:
3
1 2 3
2 3 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
global dic
dic = {'':1}
def solve(a, b, c):
	s = "".join(map(str, c))
	if s in dic:
		return dic[s]
	else:
		if len(c) == 0:
			return 1
		else:
			if a[0] == b[0]:
				dic[s] = 0
			else:
				c.remove(a[0])
				b.remove(a[0])
				a.remove(a[0])
				c.remove(b[0])
				a.remove(b[0])
				b.remove(b[0])
				ans = 0
				for i in c:
					ka = a.index(i)
					kb = b.index(i)
					kc = c.index(i)
					ans += (len(c))*(len(c)+1)*solve(a[:ka]+a[ka+1:], b[:kb]+b[kb+1:], c[:kc]+c[kc+1:])
				dic[s] = ans
			return dic[s]

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sol = solve(a, b, list(range(1, n+1)))
print(sol%1000000007)

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b, c):
	if len(c) == 0:
		return 1
	else:
		if a[0] == b[0]:
			return 0
		else:
			c.remove(a[0])
			b.remove(a[0])
			a.remove(a[0])
			c.remove(b[0])
			a.remove(b[0])
			b.remove(b[0])
			ans = 0
			for i in c:
				ka = a.index(i)
				kb = b.index(i)
				kc = c.index(i)
				ans += (len(c))*(len(c)+1)*solve(a[:ka]+a[ka+1:], b[:kb]+b[kb+1:], c[:kc]+c[kc+1:])
		
			return ans

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sol = solve(a, b, list(range(1, n+1)))
print(sol%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
n = int(raw_input())
# スペース区切りの整数の入力
a = map(int, raw_input().split())
b = map(int, raw_input().split())

if not len(a) == len(b) or not (len(a) % 3 == 0):
    raise ValueError()

def func(a, b):
    if len(a) == 0:
        return 1
    elif a[0] == b[0]:
        return 0
    else:
    	ret = 0
       	for i in a[1:]:
        	if not i == b[0]:
	            aa = a[1:]
	            aa.remove(b[0])
	            aa.remove(i)
	            bb = b[1:]
	            bb.remove(a[0])
	            bb.remove(i)
	            m = len(a) - 1
	            ret += m * (m-1) * func(aa, bb)
        return ret

ans = func(a, b)
print ans % (10**9 + 7)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
n = int(raw_input())
# スペース区切りの整数の入力
a = map(int, raw_input().split())
b = map(int, raw_input().split())

if len(a) == len(b):

def func(a, b):
    if