AT_joi2019_yo_f 座席 (Seats)

[problemUrl]: https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_f 2XXX 年，世界の国は直線状に並んでいた．$ N $ 個の国があり，$ 1,\ 2,\ ...,\ N $ の番号が付けられている．$ i\ =\ 1,\ 2,\ ...,\ N\ -\ 1 $ に対し，国 $ i $ と国 $ i\ +\ 1 $ が互いに隣国である． この年の国際情報オリンピックでは，国 $ i $ からは $ A_i $ 人の選手が参加する．国際情報オリンピックの技術委員のあなたは，競技での座席表を作成する担当である．競技会場が細長いため，一列に並んだ $ A_1\ +\ A_2\ +\ ...\ +\ A_N $ 個の座席に選手たちを割り当てることになった．不正防止のため，同じ国の選手や隣国の選手を隣り合う席に割り当ててはならない． 選手たちを座席に割り当てる方法は何通りあるだろうか．この数は非常に大きくなる可能性があるので，それを $ 10007 $ で割った余りを求めたい．

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

選手たちを座席に割り当てる方法の数を $ 10007 $ で割った余りを $ 1 $ 行で出力せよ．

### 制約 - $ 1\ ≦\ N\ ≦\ 100 $ - $ 1\ ≦\ A_i\ ≦\ 4 $ ($ 1\ ≦\ i\ ≦\ N $) ### 小課題 1. ($ 6 $ 点) $ N\ ≦\ 5 $，$ A_i\ ≦\ 2 $ ($ 1\ ≦\ i\ ≦\ N $) 2. ($ 14 $ 点) $ N\ ≦\ 10 $，$ A_i\ ≦\ 3 $ ($ 1\ ≦\ i\ ≦\ N $) 3. ($ 80 $ 点) 追加の制約はない． ### Sample Explanation 1 国 $ 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 $ ### Sample Explanation 2 この入力例では，条件を満たす座席表は存在しない． ### Sample Explanation 3 この入力例では，選手たちを座席に割り当てる方法は $ 24768 $ 通りあるため，それを $ 10007 $ で割った余りである $ 4754 $ を出力する．