座席 (Seats)
問題文
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)
入力・出力
入力
入力は以下の形式で標準入力から与えられる．
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
出力例 2
4754
この入力例では，選手たちを座席に割り当てる方法は 24768 通りあるため，それを 10007 で割った余りである 4754 を出力する．
