题目描述

有 $N$ 个块按照从左到右的顺序排列，编号从 $1$ 到 $N$。每个块都有一个权重，第 $i$ 个块的权重是 $A_i$。Snuke 将对这些块进行 $N$ 次操作：

• 选择一个尚未被移除的块，然后将它移除。这个操作的代价是与被移除的块相连的块的权重之和（包括被移除的块自身）。这里，两个块 $x$ 和 $y$ ( $x \leq y$ ) 被称为“相连”，当对于所有的 $z$ ( $x \leq z \leq y$ ) ，块 $z$ 还没有被移除。

对于所有 $N!$ 种 Snuke 移除块的顺序，计算 $N$ 个操作的总代价，并计算这 $N!$ 个总代价的和。由于答案可能非常大，所以将其对 $10^9+7$ 取模运算。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 输入数据中的所有值均为整数。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $A_1$ $A_2$ $...$ $A_N$

输出

对于所有 $N!$ 种顺序，计算 $N$ 个操作的总代价，并输出这 $N!$ 个总代价的和，对 $10^9+7$ 取模。

示例输入1

2
1 2

示例输出1

9

首先，我们考虑顺序 "块 $1$ -> 块 $2$"。在第一个操作中，操作的代价是 $1+2=3$，因为块 $1$ 和 $2$ 是相连的。在第二个操作中，操作的代价是 $2$，因为只有块 $2$ 剩下了。因此，这个顺序下的两个操作的总代价是 $3+2=5$。

然后，我们考虑顺序 "块 $2$ -> 块 $1$"。在第一个操作中，操作的代价是 $1+2=3$，因为块 $1$ 和 $2$ 是相连的。在第二个操作中，操作的代价是 $1$，因为只有块 $1$ 剩下了。因此，这个顺序下的两个操作的总代价是 $3+1=4$。

因此，答案是 $5+4=9$。

示例输入2

4
1 1 1 1

示例输出2

212

示例输入3

10
1 2 4 8 16 32 64 128 256 512

示例输出3

880971923