问题描述

在数轴上有 $N$ 个史莱姆站立着。从左边开始，第 $i$ 个史莱姆在位置 $x_i$ 处。

保证 $1 \\leq x_1 < x_2 < \\ldots < x_N \\leq 10^{9}$。

Niwango 将执行 $N-1$ 次操作。第 $i$ 次操作包括以下步骤：

• 从 $1$ 到 $N-i$（包括）以等概率选择一个整数 $k$。
• 将第 $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$ 是整数。

输入

输入从标准输入读取，具有以下格式。

$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)$ 取模。