← 返回题目列表

AtCoder · agc028_b

B. 删除块

中文机器翻译题面 查看原题

分数: 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