2XXX년, 세계의 나라는 직선으로 늘어서 있었다. 나라는 \(N\)개이고 \(1, 2, \ldots, N\)의 번호가 붙어 있다. \(i = 1, 2, \ldots, N-1\)에 대해 나라 \(i\)와 나라 \(i+1\)이 서로 이웃이다. 그해 국제정보올림피아드에는 나라 \(i\)에서 선수 \(A_i\)명이 참가한다. 당신은 기술위원으로 경기 좌석표를 만드는 일을 맡았다. 경기장이 가늘고 길어, 한 줄로 늘어선 \(A_1 + A_2 + \cdots + A_N\)개의 좌석에 선수를 배치하기로 했다. 부정 방지를 위해 같은 나라 선수나 이웃 나라 선수를 맞닿은 자리에 두면 안 된다. 선수를 좌석에 배치하는 방법의 수를 구하는 프로그램을 작성하라. 이 수는 매우 커질 수 있으므로 \(10007\)로 나눈 나머지를 구한다. |
입력은 다음 형식으로 주어진다.
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
- 첫째 줄에 나라의 수 \(N\)이 주어진다.
- 둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \ldots, A_N\)이 공백 하나로 구분되어 주어진다.
- \(1 \le N \le 100\)
- \(1 \le A_i \le 4\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 선수를 좌석에 배치하는 방법의 수를 \(10007\)로 나눈 나머지를 출력한다.
나라 \(1\)의 두 선수를 \(1\)과 \(1'\), 나라 \(2, 3, 4\)의 선수를 각각 \(2, 3, 4\)라 하면 다음 \(4\)가지 배치가 가능하다. \(1, 3, 1', 4, 2\) / \(1', 3, 1, 4, 2\) / \(2, 4, 1, 3, 1'\) / \(2, 4, 1', 3, 1\).
조건을 만족하는 좌석표는 없다.
배치 방법은 \(24768\)가지이므로, \(10007\)로 나눈 나머지 \(4754\)를 출력한다.