E - ひも 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

N 人の人が寝ている。すぬけ君は、N-1 本のひもでこの人たちを結びつけることにした。

  • それぞれのひもは、両端を異なる人に結びつけることによって、その二人を結びつけることができる。
  • どの二人も直接的または間接的にひもでつながっているようにしたい。
  • i 番目の人にはちょうど a_i 本のひもがつながっているようにしたい。

ひもの結び付け方は何通りあるか、\rm{mod}\ 1,000,000,007 で求めよ。

ひもは区別がつかないものとする。

Constraints

  • 2 \leq N \leq 100000
  • 1 \leq a_i \leq 3

Input Format

入力は以下の形式で標準入力から与えられる。 
N
a_1
:
a_N

Output Format

答えを一行に出力せよ。

Sample Input 1

9
1
3
2
1
3
1
2
1
2

Sample Output 1

1260