分数: 600 点
问题陈述
有 N 块排列成行,编号 1 to N 从左到右。 每个Block都有一个权重,Block的权重 i is A_i。 Snuke将对这些块执行以下操作 N 次:
- 选择一个仍未移除的方块,并将其移除。 此操作的成本是与要删除的块(包括其本身)相连的块的权重之和。 在这里,两个街区 x 和 y ( x \leq y )是 已连接 当,对于所有 z ( x \leq z \leq y ),块 z 仍未删除。
有 N! Snuke 移除方块的可能顺序。 对于所有这些 N! 订单,找出该订单的总成本 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
首先,我们将考虑顺序“Block 1 -> 阻止 2“。 在第一个操作中,操作的成本是 1+2=3,作为块 1 和 2 已连接。 在第二次操作中,操作成本为 2,作为唯一的块 2 仍然存在。 因此,该订单的两次操作的总成本为 3+2=5.
然后,我们将考虑顺序“Block 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