$题目描述$

小y得到了一根木材，并计划将其分成$n$段，第$i$段的质量为$m_i$。

小y需要将每一段木材分别锯开并加工。每次选择一段木材，将其连同相邻部分抬入机器，机器会锯开与相邻段相连的部分，被选择的木材会留在机器的输出区域，剩余的木材会从机器上掉到地上。

对于在地上的已经切割好的木材，小y也需要将其抬到机器的输出区域上。

小y的体力消耗定义为每次将木材抬进机器的总重量。小y有$n!$种加工顺序，想知道所有顺序下总体力消耗的和。

你只需告诉小y答案对$10^9+7$取模的结果。

$输入格式$

第一行一个正整数$n$ 。

第二行 $n$ 个正整数，其中第 $i$ 个表示$m_i$。

$输出格式$

一行一个整数表示答案。

$输入输出样例$

输入 #1

2
1 2

输出 #1

9

输入 #2

4
1 1 1 1

输出 #2

212

输入 #3

10
1 2 4 8 16 32 64 128 256 512

输出 #3

880971923

$样例1说明$

如果小y先选第 $1$ 段，再选第 $2$ 段，那么他先要把整块木材抬进机器，质量为 $3$ ，加工好第 $1$ 段后他要把第 $2$ 段木材抬进机器，花费体力为 $3+2=5$ 。

如果小y先选第 $2$ 段，再选第 $1$ 段，那么他先要把整块木材抬进机器，质量为 $3$ ，加工好第 $2$ 段后他要把第 $1$ 段木材抬进机器，花费体力为 $3+1=4$ 。

所以答案为 $5+4=9$ 。

$样例2说明$

如果小y选择的顺序是第 $2$ 段，第 $3$ 段，第 $1$ 段，第 $4$ 段，那么他先要把整块木材抬进机器，质量为 $4$ ，把木材锯成第 $1$ 段，第 $2$ 段，第 $3,4$ 段的三块。加工好第 $2$ 段后把包含第 $3,4$ 段的一块抬进机器，质量为 $2$ ，把木材锯成第 $3$ 段和第 $4$ 段的两块。加工好第 $3$ 段后把独立的第 $1$ 段抬进机器，质量为 $1$ ，加工好第 $1$ 段后把独立的第 $4$ 段抬进机器，质量为 $1$ 。此时小y需要花费的体力为 $4+2+1+1=8$ 。

由于情况较多，这里不一一列举。

$数据规模与约定$

保证 $m_i≤10^9+7$