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

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

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

9
1
3
2
1
3
1
2
1
2

1260