문제
N개의 1 이상 3 이하의 수들이 주어진다. 당신은 인접한 수 두 개 P, Q를 선택하여 그 두 수를 지우고, PneQ의 값을 집어넣는다. 여기서, PneQ는, P=Q일 땐 P이고, P≠Q일 땐 6-P-Q이다. 이 때 최종적으로 남는 수가 각각 1, 2, 3이 되게 하는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 N (1≤N≤200)을 입력한다. 두 번째 줄에는 처음에 주어지는 N개의 수들을 입력한다.
전체 데이터의 60%는 N≤50 이다.
출력
최종적으로 남는 수가 각각 1, 2, 3이 되게 하는 방법의 수를 출력한다. 답이 너무 클 수 있으므로 10,007로 나눈 나머지를 출력한다.
예제
4
1 3 3 1
2 2 2
힌트
출처
functionx
로그인해야 코드를 작성할 수 있어요.