Informatica Online Judge

  좌석 [2332 / 091C]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 5


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JOI2019예선]

Background

경곽이가 사는 세계는 현재 2XXX년, N개의 국가들은 수직선 상에 놓여있다.

각 국가들은 1, 2, ... , N 으로 번호가 부여되어 있고, 1, 2, ... , N-1에 대해서 각 국가 i와 국가 i+1은 서로 인접하다.

올해 국제정보올림피아드에는 국가 i는 A_i 명의 선수가 참가한다. 국제정보올림피아드 기술위원인 경곽이는 경기에서 좌석배치를 담당한다.

경기장의 좌석은 한 줄로 의자를 A_1 + A_2 + , ... , + A_N 개 배치하고 선수들의 자리를 배정하기로 했다.

부정행위의 방지를 위하여 같은 나라의 선수거나 인접한 나라의 선수들 끼리는 서로 옆자리를 배정하지 않기로 결정했다.

선수들을 좌석에 배정하는 방법은 몇 가지가 되는지 구하는 프로그램을 작성하시오. 단, 수가 너무 커질 수 있기 때문에 10007로 나눈 나머지를 구하시오.

Input

입력은 다음과 같은 형식으로 구성된다.

N
A_1 A_2 ... A_N

1 ≦ N ≦ 100
1 ≦ A_i ≦ 4 (1 ≦ i ≦ N)

[Sub-Task Info]
#1: (6%) N ≦ 5,A_i ≦ 2 (1 ≦ i ≦ N)
#2: (14%) N ≦ 10,A_i ≦ 3 (1 ≦ i ≦ N)
#3: (80%) 추가제한 조건은 없다.

Output

선수들을 좌석에 배정할 수 있는 경우의 수를 10007로 나눈 나머지를 출력한다.

IO Example

입력1
4
2 1 1 1

출력1
4

입력2
5
1 2 3 2 1

출력2
0

이 입력에는 조건을 만족시키는 배치는 불가능하다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]