問題文

綺麗で大きい花を人工的に作るために花びらを作りました．
それぞれの花びらは形は同じですが，色が違います．
色は $1$ から $K$ までの $K$ 色あり，色 $i$ の花びらは $C_i$ 枚あります．
この花びら全部を円形に並べて花を作ります．
作れる花として何通り存在するかを求めるプログラムを書いて下さい．
ただし，回転することで一致するものは同じ花とみなします．
上下をひっくり返して一致する場合でも，回転で一致しないのであれば，違う花とみなします．
答えは大きくなるので，$10^9+7$ で割った余りを出力して下さい．

入力

$K$
$C_1$ $C_2$ $\cdots$ $C_K$

$1 \leq K \leq 10^5$
$C_1 + C_2 + \cdots + C_K \leq 10^6$
$C_k \geq 1$

出力

作れる花のパターン数 ${\rm mod}\ 10^9+7$ の値を $1$ 行で出力して下さい．
最後に改行してください．

サンプル

2
2 2

2

2
9 1

1

3
8 1 1

9

3
3 3 3

188