問題文

妖精の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$を求めよ。

サンプル

4
1 2 3 4

43545600

2
1000 1000

1

3
1 5 3

6000