B - Fusing Slimes /

Time Limit: 2.525 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。


入力例 1

3
1 2 3

出力例 1

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

入力例 2

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

出力例 2

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

Score : 600 points

Problem Statement

There are N slimes standing on a number line. The i-th slime from the left is at position x_i.

It is guaruanteed that 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}.

Niwango will perform N-1 operations. The i-th operation consists of the following procedures:

  • Choose an integer k between 1 and N-i (inclusive) with equal probability.
  • Move the k-th slime from the left, to the position of the neighboring slime to the right.
  • Fuse the two slimes at the same position into one slime.

Find the total distance traveled by the slimes multiplied by (N-1)! (we can show that this value is an integer), modulo (10^{9}+7). If a slime is born by a fuse and that slime moves, we count it as just one slime.

Constraints

  • 2 \leq N \leq 10^{5}
  • 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}
  • x_i is an integer.

Subtasks

  • 400 points will be awarded for passing the test cases satisfying N \leq 2000.

Input

Input is given from Standard Input in the following format:

N
x_1 x_2 \ldots x_N

Output

Print the answer.


Sample Input 1

3
1 2 3

Sample Output 1

5
  • With probability \frac{1}{2}, the leftmost slime is chosen in the first operation, in which case the total distance traveled is 2.
  • With probability \frac{1}{2}, the middle slime is chosen in the first operation, in which case the total distance traveled is 3.
  • The answer is the expected total distance traveled, 2.5, multiplied by 2!, which is 5.

Sample Input 2

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

Sample Output 2

750927044
  • Find the expected value multiplied by (N-1)!, modulo (10^9+7).