레이팅 미적용설명
2XXX 年,世界の国は直線状に並んでいた. N 個の国があり, 1, 2, ..., N の番号が付けられている. i = 1, 2, ..., N - 1 に対し,国 i と国 i + 1 が互いに隣国である.
この年の国際情報オリンピックでは,国 i からは A_i 人の選手が参加する.国際情報オリンピックの技術委員のあなたは,競技での座席表を作成する担当である.競技会場が細長いため,一列に並んだ A_1 + A_2 + ... + A_N 個の座席に選手たちを割り当てることになった.不正防止のため,同じ国の選手や隣国の選手を隣り合う席に割り当ててはならない.
選手たちを座席に割り当てる方法は何通りあるだろうか.この数は非常に大きくなる可能性があるので,それを 10007 で割った余りを求めたい.
제약
1 ≦ N ≦ 100
1 ≦ A_i ≦ 4 ( 1 ≦ i ≦ N )
入力・出力
( 6 点) N ≦ 5 , A_i ≦ 2 ( 1 ≦ i ≦ N )
( 14 点) N ≦ 10 , A_i ≦ 3 ( 1 ≦ i ≦ N )
( 80 点) 追加の制約はない.
입력 형식
入力は以下の形式で標準入力から与えられる.
N
A_1 A_2 ... A_N
출력 형식
選手たちを座席に割り当てる方法の数を 10007 で割った余りを 1 行で出力せよ.
예제 1
입력
4
2 1 1 1
출력
4
예제 2
입력
5
1 2 3 2 1
출력
0
예제 3
입력
6
1 2 3 3 2 1
출력
4754
문제 정보