题目描述

有 $N$ 个方块从左到右排成一排，编号为 $1$ 到 $N$。每个方块都有一个权重，第 $i$ 个方块的权重为 $A_i$。Snuke 将对这些方块执行 $N$ 次如下操作：

• 每次选择一个尚未被移除的方块并将其移除。该操作的代价是与被移除方块相连的所有方块的权重之和（包括其本身）。这里，若两个方块 $x$ 和 $y$（$x \leq y$）之间的所有方块 $z$（$x \leq z \leq y$）都尚未被移除，则称 $x$ 和 $y$ 是相连的。

Snuke 可以以 $N!$ 种不同的顺序移除这些方块。请你对所有这 $N!$ 种移除顺序，计算每种顺序下所有操作的总代价，并求出这些总代价之和。由于答案可能非常大，请对 $10^9+7$ 取模后输出。

输入格式

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

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

第二行 $N$ 个正整数 $A_1,A_2\cdots A_n$。

输出格式

对于所有 $N!$ 种移除顺序，输出每种顺序下操作总代价之和的总和，对 $10^9+7$ 取模后输出。

样例 1

输入

2
1 2

输出

9

样例 2

输入

4
1 1 1 1

输出

212

样例 3

输入

10
1 2 4 8 16 32 64 128 256 512

输出

880971923

说明/提示

样例解释 1：

首先，我们考虑顺序为“方块 $1$ -> 方块 $2$”。在第一次操作中，由于方块 $1$ 和 $2$ 是相连的，操作代价为 $1+2=3$。在第二次操作中，只剩下方块 $2$，代价为 $2$。因此，该顺序下两次操作的总代价为 $3+2=5$。

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

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

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$