atcoder#DWACON6THPRELIMSB. Fusing Slimes

Fusing Slimes

配点 : 600600

問題文

数直線上に NN 匹のスライムが並んでいます。 左から ii 番目のスライムは位置 xix_i にいます。

ここで、1x1<x2<<xN1091 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9} が成立することが保証されます。

ニワンゴ君は操作を N1N-1 回行います。ii 回目の操作は以下の手順からなります。

  • 11 以上 NiN-i 以下の整数を等確率で選ぶ(これを kk とする)
  • 左から kk 番目にいるスライムを右隣にいるスライムの位置まで移動させる
  • その後、同じ位置にいる 22 匹のスライムを合体させ、11 匹のスライムにする

N1N-1 回の操作によって、スライムが移動した距離の総和の期待値に (N1)!(N-1)! をかけた値(これは整数になることが示せます)を 109+710^{9}+7 で割ったあまりを求めてください。なお、合体後のスライムが移動した場合は 11 体のスライムの移動として数えます。

制約

  • 2N1052 \leq N \leq 10^{5}
  • 1x1<x2<<xN1091 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}
  • xix_i は整数

部分点

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

入力

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

NN

x1x_1 x2x_2 \ldots xNx_N

出力

答えを出力せよ。

3
1 2 3
5
  • 確率 12\frac{1}{2} で最初に左から 11 番目のスライムが選ばれ、このときの移動距離の総和は 22 となります。
  • 確率 12\frac{1}{2} で最初に左から 22 番目のスライムが選ばれ、このときの移動距離の総和は 33 となります。
  • 移動距離の総和の期待値である 2.52.52!2! をかけた値である 55 が答えとなります。
12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932
750927044
  • 期待値の (N1)!(N-1)! 倍を 109+710^9+7 で割ったあまりを求めてください。