좌석

문제

2XXX 년, 세계의 나라들은 일직선으로 늘어서 있었다. $N$ 개의 나라가 있고, $1,\,2,\,...,\,N$ 의 번호가 붙어 있다. $i\,=\,1,\,2,\,...,\,N\,-\,1$ 에 대하여, 나라 $i$ 와 나라 $i\,+\,1$ 은 서로 이웃 나라이다.

이 해의 국제정보올림피아드에는 나라 $i$ 에서 $A_i$ 명의 선수가 참가한다. 국제정보올림피아드의 기술위원인 당신은 대회에서 사용할 좌석표를 작성하는 담당이다. 대회장이 가늘고 길기 때문에, 한 줄로 늘어선 $A_1\,+\,A_2\,+\,...\,+\,A_N$ 개의 좌석에 선수들을 배정하게 되었다. 부정행위를 방지하기 위해, 같은 나라의 선수나 이웃 나라의 선수를 서로 인접한 자리에 배정해서는 안 된다.

선수들을 좌석에 배정하는 방법은 몇 가지나 있을까. 이 수는 매우 커질 수 있으므로, 그것을 $10007$ 로 나눈 나머지를 구하는 프로그램을 작성하시오.

제한

• $1\,\,\le\,\,N\,\,\le\,\,100$
• $1\,\,\le\,\,A_i\,\,\le\,\,4$ ($1\,\,\le\,\,i\,\,\le\,\,N$)

서브태스크

1. ($6$ 점) $N\,\,\le\,\,5$, $A_i\,\,\le\,\,2$ ($1\,\,\le\,\,i\,\,\le\,\,N$)
2. ($14$ 점) $N\,\,\le\,\,10$, $A_i\,\,\le\,\,3$ ($1\,\,\le\,\,i\,\,\le\,\,N$)
3. ($80$ 점) 추가 제약이 없다.

입력과 출력

입력
입력은 다음 형식으로 표준 입력에서 주어진다.
$N$
$A_1$ $A_2$ $...$ $A_N$

출력
선수들을 좌석에 배정하는 방법의 수를 $10007$ 로 나눈 나머지를 $1$ 행으로 출력한다.

예제 입력 1

4
2 1 1 1

예제 출력 1

4

나라 $1$ 에서 참가하는 $2$ 명의 선수를 $1$ 과 $1'$, 나라 $2$ 에서 참가하는 $1$ 명의 선수를 $2$, 나라 $3$ 에서 참가하는 $1$ 명의 선수를 $3$, 나라 $4$ 에서 참가하는 $1$ 명의 선수를 $4$ 로 나타내기로 하면, 선수들을 좌석에 배정하는 방법으로는 다음 $4$ 가지 배열을 생각할 수 있다:

• $1$, $3$, $1'$, $4$, $2$
• $1'$, $3$, $1$, $4$, $2$
• $2$, $4$, $1$, $3$, $1'$
• $2$, $4$, $1'$, $3$, $1$

예제 입력 2

5
1 2 3 2 1

예제 출력 2

0

이 입력 예에서는 조건을 만족하는 좌석표가 존재하지 않는다.

예제 입력 3

6
1 2 3 3 2 1

예제 출력 3

4754

이 입력 예에서는 선수들을 좌석에 배정하는 방법이 $24768$ 가지 있으므로, 그것을 $10007$ 로 나눈 나머지인 $4754$ 를 출력한다.