题目描述

数直線上に $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$

输出格式

答えを出力せよ。

题目大意

有 $N$ 个史莱姆站在一条数轴上，从左数第 $i$ 个史莱姆在数轴上的位置为 $x_i$ 。

保证 $1\le x_1<x_2<...<x_n\le 10^9$ 。

Niwango将要执行 $N-1$ 次操作。第 $i$ 次操作由以下过程组成：

• 以相同的概率选择一个 $[1,n-i]$ 中的整数 $k$ 。
• 把从左数第 $k$ 个史莱姆移动到它右边的第一个史莱姆处。
• 将两个在相同位置的史莱姆融合成一个史莱姆。

请求出所有的史莱姆经过的总距离与 $(N-1)!$ 的乘积在对 $10^9+7$ 取模意义下的值（可以证明这个值是一个整数）。如果一个通过融合生成的史莱姆发生移动，我们只把它看成一个史莱姆。

3
1 2 3

5

12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932

750927044

提示

制約

• $2\ \leq\ N\ \leq\ 10^{5}$
• $ 1\ \leq\ x_1\ <\ x_2\ <\ \ldots\ <\ x_N\ \leq\ 10^{9} $
• $x_i$ は整数

部分点

• $N\ \leq\ 2000$ であるようなテストケースすべてに正解すると、$400$ 点が与えられる。

Sample Explanation 1

- 確率 $\frac{1}{2}$ で最初に左から $1$ 番目のスライムが選ばれ、このときの移動距離の総和は $2$ となります。 - 確率 $\frac{1}{2}$ で最初に左から $2$ 番目のスライムが選ばれ、このときの移動距離の総和は $3$ となります。 - 移動距離の総和の期待値である $2.5$ に $2!$ をかけた値である $5$ が答えとなります。

Sample Explanation 2

- 期待値の $(N-1)!$ 倍を $10^9+7$ で割ったあまりを求めてください。