配点 : $600$ 点

問題文

数直線上に $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$ 体のスライムの移動として数えます。

制約

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

部分点

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

入力

入力は以下の形式で標準入力から与えられる。

$N$

$x_1$ $x_2$ $\ldots$ $x_N$

出力

答えを出力せよ。

3
1 2 3

5

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

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

750927044

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