AT_nyc2015_5 ひも

[problemUrl]: https://atcoder.jp/contests/NYC2015/tasks/nyc2015_5 入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ : $ a_N $ 答えを一行に出力せよ。 ``` 9 1 3 2 1 3 1 2 1 2 ``` ``` 1260 ```

N/A

N/A

### Constraints $ N $ 人の人が寝ている。すぬけ君は、$ N-1 $ 本のひもでこの人たちを結びつけることにした。 - それぞれのひもは、両端を異なる人に結びつけることによって、その二人を結びつけることができる。 - どの二人も直接的または間接的にひもでつながっているようにしたい。 - $ i $ 番目の人にはちょうど $ a_i $ 本のひもがつながっているようにしたい。 ひもの結び付け方は何通りあるか、$ \rm{mod}\ 1,000,000,007 $ で求めよ。 ひもは区別がつかないものとする。 - - - - - - - $ 2\ \leq\ N\ \leq\ 100000 $ - $ 1\ \leq\ a_i\ \leq\ 3 $