No.856 増える演算

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : CuriousFairy315CuriousFairy315 / テスター : kakira9618kakira9618
2 ProblemId : 2838 / 出題時の順位表

問題文

妖精の31536000は、足し算や掛け算、指数のような値が増えるものが好きです。
そこで、数字を$N$個書き、これらを次の規則に従って計算することにしました。
まず全ての$i < j$となる$i$及び$j$を選び、$(A_i + A_j) \cdot A_i^{A_j}$を掛け合わせます。
ですがこの値はちょっと大きかったので、$(A_i + A_j) \cdot A_i^{A_j}$のうち最も小さいものを選んで割ったところ、値が$M$になりました。
さて、この$M$はいくつだったでしょうか?
ただ、答えは非常に大きくなる可能性があるので、$M$の代わりに$M$を$1000000007$で割ったあまりを出力してください。

入力

$N$
$A_1$ $\cdots$ $A_N$

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^5$

出力

$\displaystyle \frac{\prod_{i=1}^{N} \prod_{j=i+1}^{N} (A_i + A_j) \cdot A_i^{A_j}}{\underset{i < j}{\min}((A_i + A_j) \cdot A_i^{A_j})} \mod 1000000007$を求めよ。

サンプル

サンプル1
入力
4
1 2 3 4
出力
43545600

$(1 + 2) \cdot 1^2 \cdot (1 + 3) \cdot 1^3 \cdot (1 + 4) \cdot 1^4 \cdot (2 + 3) \cdot 2^3 \cdot (2 + 4) \cdot 2^4 \cdot (3 + 4) \cdot 3^4 = 3 \cdot 4 \cdot 5 \cdot 40 \cdot 96 \cdot 567 = 130636800$です。
また、割った値は$3$なので、答えは$130636800/ 3 = 43545600$です。

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

$\frac{(1000 + 1000) \cdot 1000^{1000}}{(1000 + 1000) \cdot 1000^{1000}} = 1$です。

サンプル3
入力
3
1 5 3
出力
6000

$\frac{(1+5) \cdot 1^5 \cdot (1+3) \cdot 1^3 \cdot (5+3) \cdot 5^3}{(1+3) \cdot 1^3}=6000$です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。