Description

有$n$堆石子,每次从中抽取两堆进行合并，合并后的石子数记做权，并把合并后的石子堆当做新的一堆放回，重新随机抽取两堆石子，重复上面的操作，直到所有石子合并成一堆，则每次合并的和的总和是多少？

Format

Input

第一行：石子的堆数$n(1 <= n <= 10000)。$ 第二行：每堆石子的石子数$a_i$$(1 <= a_i <= 10000)$

Output

每次合并的权的最大总和（由于最后的结果较大，请对最终的结果$mod1000000007$）

Samples

3
6 7 10

40

Hint

先合并7和10，得到17，再将17与6合并得到23