/ 
実行時間制限: 2.525 sec / メモリ制限: 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.5 に 2! をかけた値である 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).