可以发现，每组操作唯一对应一个长度为 (n-1) 的排列。有了这个结论，后面就好做多了。
像这类排列，与期望相关的题目，我们一般都不需要得到整个完整的排列，而是从排列中拆一段贡献出来算，这题也是一样。
非常 ( ext{Naive}) 的想法：设 (E[X]) 为期望移动距离和，有 (E[X]=sumlimits_{i=1}^{n-1}E[i])，其中 (E[i]) 是第 (i) 次期望移动的距离。这样不太好算。不妨换个想法，设 (E[i]) 为 (x_i o x_{i+1}) 这一段被经过的期望次数。如果我们能够计算出每个 (E[i]) ，把它乘上 ((x_{i+1}-x_i)) ，就是 (x_i o x_{i+1}) 这一段期望移动的距离和。
按照套路，(E[i]=sumlimits_{j=1}^{i} p_{i,j})，其中 (p_{i,j}) 为第 (j) 个点经过 (x_i o x_{i+1}) 的概率，根据期望的线性性质，这是显然的。
现在尝试计算出 (p_{i,j})。有：
[p_{i,j}=frac{1}{(n-1)!}sum_{k=i-j}^{n-2}inom{k}{i-j}(i-j)!(n-2-(i-j))!
]
很容易可以算出 (p_{i,j}=frac{1}{i-j+1})。回带可得：
[E[X]=sum_{i=1}^{n-1}(x_{i+1}-x_i)sum_{j=1}^ifrac{1}{j}
]
前缀和处理一下，可以做到 (O(n log n))。记得答案最后是 (E[X] imes(n-1)!)（
#include<cstdio>
#define int ll
typedef long long ll;
const int mod=1e9+7;
int pref[100005],x[100005];
inline int read() {
register int x=0,f=1;register char s=getchar();
while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
return x*f;
}
inline int pow(int x,int p) {int res=1;for(;p;p>>=1) {if(p&1) res=res*x%mod; x=x*x%mod;}return res;}
signed main() {
int n=read(),ans=0;
for(register int i=1;i<=n;++i) x[i]=read();
for(register int i=1;i<=n;++i) pref[i]=(pref[i-1]+pow(i,mod-2))%mod;
for(register int i=1;i<n;++i) ans=(ans+(x[i+1]-x[i])*pref[i]%mod)%mod;
for(register int i=1;i<n;++i) ans=ans*i%mod;
printf("%lld
",ans);
return 0;
}