問題一覧 > 通常問題

No.125 悪の花弁

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : LayCurseLayCurse
6 ProblemId : 167 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:58

問題文

綺麗で大きい花を人工的に作るために花びらを作りました.
それぞれの花びらは形は同じですが,色が違います.
色は $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$ 行で出力して下さい.
最後に改行してください.

サンプル

サンプル1
入力
2
2 2
出力
2

同じ色の花びらが隣り合っているか,交互に並んでいるかの $2$ 通りが存在します.

サンプル2
入力
2
9 1
出力
1

$1$ 枚だけ色の違う花びらがありますが,回転すれば全部一致してしまいます.

サンプル3
入力
3
8 1 1
出力
9

色 $2$ の花びらを固定した時,色 $3$ の花びらがどこに配置されるかで $9$ 通りの花を作ることができます.
鏡像反転して一致しても,回転して一致しないものは違う花とみなすことに注意して下さい.

サンプル4
入力
3
3 3 3
出力
188

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。