AT_dwacon6th_prelims_b Fusing Slimes

在数轴上有 $N$ 只史莱姆排成一列。从左到右第 $i$ 只史莱姆位于位置 $x_i$。 这里保证 $1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}$。 “ニワンゴ君”将进行 $N-1$ 次操作。第 $i$ 次操作的步骤如下： - 从 $1$ 到 $N-i$ 之间等概率地选择一个整数（记为 $k$）。 - 将从左数第 $k$ 只史莱姆移动到其右侧相邻史莱姆的位置。 - 随后，将同一位置上的 $2$ 只史莱姆合并为 $1$ 只史莱姆。 经过 $N-1$ 次操作后，求史莱姆移动的距离总和的期望值乘以 $(N-1)!$（可以证明这是整数），再对 $10^{9}+7$ 取模的结果。注意，合并后的史莱姆如果发生移动，只计为 $1$ 只史莱姆的移动。

输入通过标准输入按以下格式给出。 > $N$ $x_1$ $x_2$ $\ldots$ $x_N$

请输出答案。

## 限制条件 - $2 \leq N \leq 10^{5}$ - $1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}$ - $x_i$ 是整数 ## 部分得分 - 如果你能正确解决所有 $N \leq 2000$ 的测试用例，将获得 $400$ 分。 ## 样例解释 1 - 以概率 $\frac{1}{2}$ 首先选择从左数第 $1$ 只史莱姆，此时移动距离总和为 $2$。 - 以概率 $\frac{1}{2}$ 首先选择从左数第 $2$ 只史莱姆，此时移动距离总和为 $3$。 - 移动距离总和的期望值为 $2.5$，乘以 $2!$ 得到 $5$，即为答案。 ## 样例解释 2 - 请计算期望值的 $(N-1)!$ 倍对 $10^9+7$ 取模的结果。 由 ChatGPT 4.1 翻译