分数: 600 点
问题陈述
有 N 史莱姆站在数轴上。 的 i左边第一个史莱姆位于位置 x_i.
保证 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}.
Niwango 将表演 N-1 操作。 i第次操作由以下过程组成:
- 选择一个整数 k 之间 1 和 N-i (含)等概率。
- 移动 k从左侧开始的第一个史莱姆,到右侧相邻史莱姆的位置。
- 将同一位置的两个史莱姆融合成一个史莱姆。
求史莱姆移动的总距离乘以 (N-1)! (我们可以证明这个值是一个整数),模 (10^{9}+7)。如果史莱姆是通过导火线诞生的,并且该史莱姆会移动,我们将其视为一个史莱姆。
约束
- 2 \leq N \leq 10^{5}
- 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}
- x_i 是一个整数。
子任务
- 400 通过满足以下条件的测试用例将获得积分 N \leq 2000.
输入
输入由标准输入按以下格式给出:
N x_1 x_2 \ldots x_N
输出
打印答案。
示例输入 1
3 1 2 3
示例输出 1
5
- 有概率 \frac{1}{2},在第一次操作中选择最左边的史莱姆,在这种情况下,移动的总距离为 2.
- 有概率 \frac{1}{2},在第一次操作中选择中间的史莱姆,在这种情况下,移动的总距离为 3.
- 答案是预期的总行驶距离, 2.5,乘以 2!,即 5.
示例输入 2
12 161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932
示例输出 2
750927044
- 求期望值乘以 (N-1)!,模数 (10^9+7).