填空题

魔法排列

Question

众所周知，集合{1 2 3 … N}有N!种不同的排列，假设第i个排列为P_i且P_i,j是该排列的第j个数。将N个点放置在x轴上，第i个点的坐标为x_i且所有点的坐标两两不同。对于每个排列（以P_i为例），可以将其视为对上述N个点的一种遍历顺序，即从第P_i,1个点出发，沿直线距离到达第P_i,2个点，再沿直线距离到达第P_i,3个点，以此类推，最后到达第P_i,N个点，将该路线的总长度定义为L(P_i)，那么所有N!种路线的总长度之和是多少，即L(P₁)+L(P₂)+L(P₃)+...+L(P_N!)的结果是多少？

输入描述：

第一行包含一个整数N，1≤N≤10⁵。

第二行包含N个空格隔开的整数x₁到x_N，0≤x₁<x₂<x₃<...<x_N≤10⁹。

输入样例： 3 0 1 3 输出描述：

输出L(P₁)+L(P₂)+L(P₃)+...+L(P_N!)对10⁹+7取模后的结果。

输出样例 24