問題文

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. ($6$ 点) $N ≦ 5$，$A_i ≦ 2$ ($1 ≦ i ≦ N$)
2. ($14$ 点) $N ≦ 10$，$A_i ≦ 3$ ($1 ≦ i ≦ N$)
3. ($80$ 点) 追加の制約はない．

入力例 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$ を出力する．