Problem:
 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) .

Solution (Python):
mod = 10 ** 9 + 7

def fact(n):
    res = 1
    for i in range(2, n + 1):
        res = (res * i) % mod
    return res


N, *X = map(int, open(0).read().split())

ans = 0
for i in range(N - 1):
    ans += (X[-1] - X[i]) * pow(i + 1, mod - 2, mod)
    ans %= mod

print(ans * fact(N - 1) % mod)

Solution (Python):
MOD = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
x.sort()

kaijo = [1]
for i in range(1, N):
    kaijo.append(kaijo[-1] * i % MOD)

ans = 0
for i in range(N - 1):
    ans = (ans * (i + 1) + (x[-1] - x[i]) * kaijo[i]) % MOD

print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split());_=10**9+7;x=m=1;z=0
for i in range(2,n):x=m=m*i%_
for i in range(n):z=z+x*(a[i]-a[i-1])%_;x=x+m*pow(i+1,_-2,_)%_
print(z%_)

Solution (Python):
N,*X=map(int,open(0).read().split());M,g,q,r=10**9+7,1,[1,1],0
for i in range(1,N):r,g=(r+q[-1]*(X[-1]-X[i-1]))%M,g*i%M;q+=[M//(-~i)*-q[M%(-~i)]%M]
print(r*g%M)

Solution (Python):
import math

n = int(input())
x = [0] + list(map(int, input().split()))
mod = 10**9 + 7

s = [pow(i, mod-2, mod) for i in range(0,n+1)]
for i in range(n):
    s[i+1] = (s[i+1] + s[i]) % mod

ans = 0
for i in range(1,n):
    ans += ((x[i+1] - x[i]) * s[i]) % mod
ans = int(ans * math.factorial(n-1)) % mod
print(ans)

Solution (Python):
MOD = 10**9 + 7
N = int(input())
X = list(map(int, input().split()))
D = [dj - di for di, dj in zip(X, X[1:])]

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def framod(n, a=1, mod=10**9+7):
    for i in range(1,n+1):
        a = a * i % mod
    return a

count_d = []
frac_Nm1 = framod(N-1)
for i in range(1, N):
  count_d.append(frac_Nm1 * power(i, MOD-2) % MOD)

for i in range(1, N-1):
  count_d[i] += count_d[i-1]


ans = sum([d*c % MOD for d, c in zip(D, count_d)]) % MOD
print(ans)

Solution (Python):
n = int(input())
x = list(map(int, input().split()))
ans = 0
mod = 1000000007
p = 1
for i in range(1, n):
  p *= i
  p %= mod
for i in range(n-1):
  ans += (x[n-1]-x[i])*pow(i+1, mod-2, mod)
ans *= p
ans %= 1000000007
print(ans)

Solution (Python):
n = int(input())
x = list(map(int, input().split()))
ans = 0
mod = 1000000007
p = 1
for i in range(1, n):
  p *= i
  p %= mod
for i in range(n-1):
  ans += (x[n-1]-x[i])*pow(i+1, mod-2, mod)
ans *= p
ans %= 1000000007
print(ans)

Solution (Python):
import sys
import math
sys.setrecursionlimit(10**9)
MOD = 10**9+7

N = int(input())
*B, = map(int,input().split())
A = []
for i in range(N-1):
    A.append(B[i+1]-B[i])

S = []
f = math.factorial(N-1)
cur = 0
for i in range(1,N):
    cur += pow(i,MOD-2,MOD)
    S.append(cur)

sm  = 0
for a,b in zip(A,S):
    sm += (a*b)%MOD

print((sm*f)%MOD)

Solution (Python):
def b_fusing_slimes(MOD=10**9 + 7):
    from math import factorial
    N = int(input())
    X = [int(i) for i in input().split()]

    diff = [0] + [X[i + 1] - X[i] for i in range(N - 1)]
    cumsum = [0]
    for j in range(1, N):
        cumsum.append((cumsum[-1] + pow(j, MOD - 2, MOD)) % MOD)

    ans = sum([(diff[i] * cumsum[i]) % MOD for i in range(1, N)]) % MOD
    return (ans * factorial(N - 1)) % MOD

print(b_fusing_slimes())

Solution (Python):
N,*X=map(int,open(0).read().split())
M,g,q,r=10**9+7,1,[1,1],0
for i in range(1,N):
 r,g=(r+q[-1]*(X[-1]-X[i-1]))%M,g*i%M
 q+=[M//(-~i)*-q[M%(-~i)]%M]
print(r*g%M)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

n = int(input())
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(n - 1)]

def pow(x, y):
    if y == 0:
        return 1
    ans = 1
    while y > 1:
        if y % 2 != 0:
            ans *= x
            ans %= 1000000007
        x *= x
        x %= 1000000007
        y //= 2
    return ans * x % 1000000007

def fact(m):
  return m * fact(m-1) % 1000000007 if m != 1 else 1
 
fact_n_1 = fact(n-1)

e = [None] * (n-1)
for i in range(n-1):
  if i == 0:
    e[i] = fact_n_1
  else:
    e[i] = (e[i - 1] + fact_n_1 * pow(i + 1, 1000000005)) % 1000000007

print(sum(e_i * d_i % 1000000007
          for i, (d_i, e_i) 
          in enumerate(zip(d, e))) % 1000000007 )

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    def modinv(a, mod):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    N=int(input())
    x=list(map(int,input().split()))
    z=[0]*N
    z[0]=1
    for i in range(N-1):
        z[0]*=i+1
        z[0]%=MOD
    ans=0
    for i in range(N-1):
        ans+=(x[i+1]-x[i])*z[i]
        ans%=MOD
        z[i+1]=z[i]+z[0]*modinv(i+2,MOD)
        z[i+1]%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappop, heappush
from fractions import Fraction

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


N = int(input())
X = list(map(int, input().split()))
MOD = 10**9+7

MAXN = N+5
fac = [1, 1] + [0] * MAXN
inv = [0, 1] + [0] * MAXN


for i in range(2, N):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = modinv(i, MOD)


c = 0
t = 0
f = fac[N-1]

for i in range(0, N-1):
    x = X[i+1] - X[i]
    c += f * inv[i+1]
    c %= MOD
    t += c * x
    t %= MOD

print(t)

Solution (Python):
n=int(input());a=list(map(int,input().split()));mod=10**9+7;x=m=1;z=0
for i in range(2,n):x=m=m*i%mod
for i in range(n):z=z+x*(a[i]-a[i-1])%mod;x=x+m*pow(i+1,mod-2,mod)%mod
print(z%mod)

Solution (Python):
n = int(input())
lst1 = list(map(int,input().split()))
mod = 10**9+7
def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
fac = [1]

for i in range(n-1):
    fac.append(fac[-1]*(i+1)%mod)

f = 1
ans = 0
for i in range(n-1):
    ans += ((lst1[-1]-lst1[i])*fac[-1]*pow(i+1,mod-2))%mod
print(ans%mod)

Solution (Python):
n = int(input())
x = list(map(int, input().split()))

mod = 10**9 + 7

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

ans = 0
j_inv = []
num = 0
for j in range(1, n):
    num += inv[j]
    num %= mod
    j_inv.append(num)

for i in range(n-1):
    ans += j_inv[i] * (x[i+1] - x[i])
    ans %= mod

ans *=fac[n-1]
ans %= mod

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
m=1
for i in range(2,n):m=m*i%mod
ans=0
x=m
for i in range(n):
  ans=(ans+x*(a[i]-a[i-1]))%mod
  x=(x+m*pow(i+1,mod-2,mod))%mod
print(ans)

Solution (Python):
N = int(input())
X = list(map(int,input().split()))
import math
ans = 0
mod = 10**9+7
a = 0
ans = 0
for i in range(N-1):
  a += pow(i+1,mod-2,mod)
  ans += ((X[i+1]-X[i])%mod)*(a%mod)
  ans %= mod
  
ans *= math.factorial(N-1)%mod

print(ans%mod)

Solution (Python):
def modinv2(a,m):
    return pow(a,m-2,m)

def f(n,m):
    a = 1
    for i in range(2,n+1):
        a = a*i%m
    return a

N = int(input())
x = list(map(int,input().split()))

ans = 0
P = 10**9+7

b = f(N-1,P)

invlist = [1]

for i in range(1,N-1):
    inv = (invlist[-1]+modinv2(i+1,P))%P
    invlist.append(inv)


for i in range(N-1):
    l = x[i+1]-x[i]
    ans += (l*invlist[i]%P)*b%P

print(ans%P)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.read

N, *x = map(int, read().split())
mod = 10 ** 9 + 7
'''
x_(i+1)が選ばれる前にx_iが選ばれれば, x_(i+1)-x_iを加算
(N-1)!通りの中でこのような状況はsum (N-i)! i=2toN-1

x_(i+n)が選ばれる前、かつx_(i+1)からx_(i+n-1)が選ばれた後にx_iが選ばれれば, x_(i+n)-x_iを加算

'''
inv = [0] * N
for i in range(1, N):
    inv[i] = pow(i, mod - 2, mod)

for i in range(2, N):
    inv[i] = (inv[i] + inv[i - 1]) % mod

fact = 1
for i in range(1, N):
    fact *= i
    fact %= mod

x = np.array(x, np.int64)
X = x[1:] - x[:-1]
inv = np.array(inv[1:], np.int64)

answer = X * inv % mod * fact % mod
print(answer.sum() % mod)

Solution (Python):
N = int(input())
Xs = list(map(int, input().split()))
mod = 10**9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
g1 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

mxx = Xs[-1]
r = 0
r2 = 0
for i in range(N-1):
    r = (r+mul(mul(g1[N-1],inverse[i+1]),Xs[N-1]-Xs[i]))%mod
print(r)

Solution (Python):
import sys

read = sys.stdin.read

N, *x = map(int, read().split())
mod = 10 ** 9 + 7
'''
x_(i+1)が選ばれる前にx_iが選ばれれば, x_(i+1)-x_iを加算
(N-1)!通りの中でこのような状況はsum (N-i)! i=2toN-1

x_(i+n)が選ばれる前、かつx_(i+1)からx_(i+n-1)が選ばれた後にx_iが選ばれれば, x_(i+n)-x_iを加算

'''
inv = [0] * N
for i in range(1, N):
    inv[i] = pow(i, mod - 2, mod)

for i in range(2, N):
    inv[i] = (inv[i] + inv[i - 1]) % mod

fact = 1
for i in range(1, N):
    fact *= i
    fact %= mod

answer = 0
for i, j, k in zip(inv[1:], x, x[1:]):
    tmp = (i * fact) % mod
    answer += tmp * (k - j) % mod
    answer %= mod

print(answer)

Solution (Python):
from math import factorial
 
N = int(input())
lst = [int(x) for x in input().split(" ")]
mod = 10**9 + 7
dists = [lst[i+1] - lst[i] for i in range(N-1)]
ans = 0
m = N - 1
fac = factorial(m) % mod
tmp = fac

for i in range(m):
    ans += dists[i] * tmp
    ans %= mod
    tmp += fac*pow((i+2), (mod-2), mod) % mod
    
print(ans)

Solution (Python):
from math import factorial
 
N = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
x_dis = [x[i+1] - x[i] for i in range(N-1)]
ans = 0
m = N-1
fac = factorial(m) % mod
tmp = fac
for i in range(m):
    ans += x_dis[i] * tmp
    ans %= mod
    tmp += (fac*pow((i+2),(mod-2), mod))%mod
print(ans)

Solution (Python):
N, *X = map(int, open(0).read().split())

MOD = 10 ** 9 + 7

fact = 1
for i in range(2, N):
    fact = fact * i % MOD

fact_list = [fact]
for i in range(2, N):
    fact_list.append(fact_list[-1] + fact * pow(i, MOD - 2, MOD) % MOD)

ans = 0
for i in range(N - 1):
    ans = (ans + (X[i + 1] - X[i]) * fact_list[i]) % MOD
    
print(ans % MOD)

Solution (Python):
import math

n = int(input())
x = list(map(int,input().split()))

mod = 10**9 + 7

f = math.factorial(n-1)
f %= mod

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

l = []
for i in range(n-1):
    d = x[i+1] - x[i]
    l.append(d)



count = 0
k = f
plus = 0
for i in range(1,n):
    
    k = f + plus
    count += l[i-1] * k
    plus += f * modinv(i+1,mod)

print(int(count)%mod)

Solution (Python):
N = int(input())
x = list(map(int, input().split()))
MOD = 10**9+7
D = x[-1]-x[0]
ans = 0
fact = [1]

for i in range(1, N):
    fact.append(fact[-1]*i%MOD)

inv_table = [-1]*N

for i in range(N):
    inv_table[i] = pow(i, MOD-2, MOD)
    
for i in range(N-1):
    d = D-(x[i]-x[0])
    ans += d*fact[N-1]*inv_table[i+1]
    ans %= MOD

print(ans)

Solution (Python):
from math import factorial

N = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
x_dis = [x[i+1] - x[i] for i in range(N-1)]
ans = 0
m = N-1
fac = factorial(m) % mod
tmp = fac
for i in range(m):
    ans += x_dis[i] * tmp
    ans %= mod
    tmp += (fac*pow((i+2),(mod-2), mod))%mod
print(ans)

Solution (Python):
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

n = int(input())
a = list(map(int, input().split()))
MOD = 10**9 + 7
comb = Combination(n, MOD)

effi = [0] * n
effi[0] = 1
for i in range(n - 1):
    effi[i + 1] = effi[i] + pow(i + 2, MOD - 2, MOD)
    effi[i + 1] %= MOD

ans = 0
for i in range(n - 1):
    ans += effi[i] * (a[i+1] - a[i])
    ans %= MOD

print(ans * comb.factorial(n - 1) % MOD)

Solution (Python):
from math import factorial

mod = 10**9+7
N = int(input())
x = [0] + list(map(int, input().split()))
ans = 0
inv = [0] + [pow(i, mod-2, mod) for i in range(1, N)]

for k in range(2, N):
    ans = (ans + x[k] * (1 - inv[k])) % mod

for k in range(1, N-1):
    ans = (ans - x[k] * (1 - inv[N-k])) % mod

for k in range(1, N):
    ans = (ans + (x[N] - x[k]) * inv[N-k]) % mod

ans = ans * factorial(N-1) % mod

print(ans)

Solution (Python):
n = int(input())
x = list(map(int,input().split()))

P = 10**9 + 7
mo = P
inv_t = [0]+[1]
for i in range(2,n):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]


d = []
for i in range(n-1):
    d.append(x[i+1] - x[i])

kai = 1
for i in range(n-2):
    kai = kai*(i+2)
    kai = kai%mo 

rui = []
tmp = 0
for i in range(n-1):
    tmp += d[-i-1]
    tmp = tmp%mo
    rui.append(tmp)





ans = 0
for i in range(n-1):
    
    fa = kai*inv_t[n-i-1]
    fa = ( (fa%mo)*(rui[i]%mo) )%mo
    ans += fa
    ans = ans%mo

print(ans%mo)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
import numpy as np
 
MOD = 10 ** 9 + 7
 
N = int(readline())
X = np.array(read().split(),np.int64)
 
def cumprod(A, MOD = MOD):
    L = len(A); Lsq = int(L**.5+1)
    A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        A[:,n] *= A[:,n-1]; A[:,n] %= MOD
    for n in range(1,Lsq):
        A[n] *= A[n-1,-1]; A[n] %= MOD
    return A.ravel()[:L]
def make_fact(U, MOD = MOD):
    x = np.arange(U, dtype = np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact,fact_inv
 
U = 10 ** 5 + 5
fact, fact_inv = make_fact(U)
 
inv = np.zeros(U,np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
 
coef = inv[1:N].cumsum() % MOD
 
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]; answer %= MOD
 
print(answer)

Solution (Python):
def solve():
    MOD = 10**9 + 7

    N = int(input())
    xs = list(map(int, input().split()))

    ds = []
    for i in range(N-1):
        d = xs[i+1] - xs[i]
        ds.append(d)

    nums = [1, 1]
    num = 1
    for i in range(2, N-1):
        num *= i
        num %= MOD
        nums.append(num)

    ms = [N-1]
    m = N-1
    for i in reversed(range(2, N-1)):
        m *= i
        m %= MOD
        ms.append(m)
    ms.reverse()
    ms.append(1)

    ks = []
    k = 0
    for num, m in zip(nums, ms):
        k += num*m % MOD
        k %= MOD
        ks.append(k)

    ans = 0
    for d, k in zip(ds, ks):
        ans += d*k % MOD
        ans %= MOD

    print(ans)

solve()

Solution (Python):
n = int(input())
x = list(map(int, input().split()))

x_diff = []
for i in range(n-1):
    x_diff.append(x[i+1] - x[i])



def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

base = 1
for i in range(1, n):
    base *= i
    base %= 10**9+7

frac = []
for i in range(1, n):
    frac.append(base*modinv(i) % (10**9+7))

import itertools
frac = list(itertools.accumulate(frac))

ans = 0
for i in range(n-1):
    ans += frac[i]*x_diff[i]
    ans %= 10**9+7

print(ans)

Solution (Python):
n = int(input())
x = list(map(int, input().split()))

x_diff = []
for i in range(n-1):
    x_diff.append(x[i+1] - x[i])



def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

base = 1
for i in range(1, n):
    base *= i
    base %= 10**9+7

frac = []
for i in range(1, n):
    frac.append(base*modinv(i) % (10**9+7))

import itertools
frac = list(itertools.accumulate(frac))

ans = 0
for i in range(n-1):
    ans += frac[i]*x_diff[i]
    ans %= 10**9+7

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    @lru_cache(maxsize=None)
    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(N, X):
    M = Mod(10**9+7)
    ne = 1
    for i in range(2, N):
        ne = M.mul(i, ne)
    ans = 0
    p = 0
    for i in range(N-1):
        d = X[i+1] - X[i]
        p = M.add(p, M.div(ne, i+1))
        ans = M.add(ans, M.mul(d, p))
    return ans

def main():
    N = read_int()
    X = read_int_n()
    print(slv(N, X))

if __name__ == '__main__':
    main()

Solution (Python):
import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


n = int(input())
xxx = list(map(int, input().split()))
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)

ans = 0
dp = 1
for i in range(n - 1):
    cur = dp * factorials[i] % MOD
    ans = (ans + (xxx[i + 1] - xxx[i]) * cur * invs[i + 1]) % MOD
    dp = (dp + (cur + factorials[i + 1]) * invs[i + 1]) % MOD
ans = ans * factorials[n - 1] % MOD
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    @lru_cache(maxsize=None)
    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(N, X):
    M = Mod(10**9+7)
    ne = [1]
    for i in range(1, N+1):
        ne.append(M.mul(i, ne[i-1]))
    ans = 0
    p = 0
    for i in range(N-1):
        d = X[i+1] - X[i]
        p = M.add(p, M.div(ne[N-1], i+1))
        ans = M.add(ans, M.mul(d, p))
    return ans

def slv2(N, X):
    ans = 0
    s = Counter()
    for p in permutations(range(N-1)):
        x = X[:]
        for i in p:
            for j in range(i+1, N):
                if x[j]:
                    break

            ans += x[j] - x[i]
            s[(j, i)] += 1
            x[i] = None
    for i in range(N-1):
        for j in range(i+1, N):
            print(i, j, s[(j,i)])
    return ans

def main():
    N = read_int()
    X = read_int_n()
    print(slv(N, X))
    

    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
x = list(map(int, input().split()))
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N, mod)
res = 0
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] * (i + 1) + f.factorial(i) % mod
  t[i + 1] %= mod

for i in range(N - 2, -1, -1):
  res += (x[i + 1] - x[i]) * t[i + 1] * f.factorial(N - 1) % mod * f.ifactorial(i + 1) % mod
  res %= mod
print(res)

Solution (Python):
N=int(input())
X=list(map(int,input().split()))
MOD=10**9+7

facN_1=1
suminv=[1]*N
inv=[1]*N
for i in range(2,N):
    facN_1=facN_1*i%MOD
    inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
    suminv[i]=(suminv[i-1]+inv[i])%MOD

ans=0
for i in range(N-1):
    tmp=X[i+1]-X[i]
    tmp*=suminv[i+1]%MOD
    ans+=tmp
    ans%=MOD
print(ans*facN_1%MOD)

Solution (Python):
from itertools import*
n,*c=map(int,open(0).read().split())
mod=10**9+7
dif=[j-i for i,j in zip(c,c[1:])]
fac=[1]*n
for i in range(1,n):
	fac[i]=fac[i-1]*i%mod
inv=[pow(i,mod-2,mod) for i in range(n)]
acc_inv=list(accumulate(inv))
ans=0
for k in range(1,n):
	ans+=dif[k-1]*acc_inv[k]
	ans%=mod
print(ans*fac[-1]%mod)

Solution (Python):
import sys
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=n
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)


ans=0
DP=[0]*n
DP[0]=1
DP[1]=1
ans=(ans+DP[1]*(X[1]-X[0])*F[n-1]*FI[0])%mod
for i in range(2,n):
  DP[i]=(F[i-1]+DP[i-1]*i)%mod
  ans=(ans+DP[i]*(X[i]-X[i-1])*F[n-1]*FI[i])%mod
print(ans)

Solution (Python):
n = int(input())
x = list(map(int,input().split()))
mod = 10**9+7


y = []
for i in range(1,n):
    y.append(x[i]-x[i-1])



p = []
q = 1
last = 1
fac = 1

for i in range(2,n):
    last = (last*i+fac)%mod
    fac = fac*i%mod
    p.append(last*pow(fac*q,mod-2,mod)%mod)
    q = q*p[-1]%mod


res = 0
r = fac
for i in range(n-1):
    res = (res + y[i]*r)%mod
    if i != n-2:
        r = (r*p[i])%mod
print(res%mod)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7
    from math import factorial
    N = II()
    X = LMIIS()
    f = factorial(N-1) % MOD
    def calc(k,slimes):
        r = 0
        for k in range(N-1):
            r += (slimes[-1]-slimes[-2-k]) * f * pow((N-k-1),MOD-2,MOD)
            r %= MOD
        return r
    print(calc(0,X))


if __name__ == '__main__':
    main()

Solution (Python):
import math

n = int(input())
x = list(map(int, input().split()))
mod = 10 ** 9 + 7

fac = math.factorial(n - 1) % mod


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


res = 0
for i in range(n - 1):
    d = x[n - 1] - x[i]
    res += (d * fac * pow(i + 1, mod - 2)) % mod

print(res % mod)

Solution (Python):
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import functools
N = int(input())
x = [int(i) for i in input().split()]
mod = 10**9+7
start = 1
st = 1
st_list = [0] * N
st_rev = [0] * N
for i in range(N-1):
    st *= (i+1)
    st %= mod
    st_list[i] = st
    st_rev[i] = pow(st,mod-2,mod)
all_dis = 0
for i in range(N-1):
    far = x[i+1]-x[i]
    all_dis += far*start*st_list[N-2]*st_rev[i]
    start = (start*(i+2)+st_list[i])%mod
    all_dis %= mod
print(all_dis)

Solution (Python):
MOD = 10**9+7
n = int(input())
m = n - 1
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(m)]

inv = [0, 1]
for i in range(2, n):
  inv += [inv[MOD % i] * (MOD - int(MOD / i)) % MOD]

s = 1
for i in range(2, n):
    s *= i
    s %= MOD

ans = s * sum(d) % MOD

p = 0
for i in range(1, m):
    p += inv[i+1]
    p %= MOD
    ans += s * d[i] * p
    ans %= MOD

print(ans)

Solution (Python):
MOD=10**9+7
N=int(input())
x=list(map(int, input().split()))
y=[x[i+1]-x[i] for i in range(N-1)]

upp=[1]*(N+1)
for i in range(2, N+1):
  upp[i]=upp[i-1]*i
  upp[i]%=MOD
  
inv=[1]*(N+1)
inv[-1]=pow(upp[-1], MOD-2, MOD)
for i in range(N, 1, -1):
  inv[i-1]=inv[i]*i%MOD

a=[0]*(N-1)
a[0]=upp[N-1]
for i in range(1, N-1):
  a[i]=a[0]*pow(i+1, MOD-2, MOD)
  a[i]%=MOD

b=[0]*(N-1)
b[0]=a[0]
for i in range(1, N-1):
  b[i]=b[i-1]+a[i]
  b[i]%=MOD
  
def moddot(v1, v2):
  n=len(v1)
  out=0
  for i in range(n):
    out+=v1[i]*v2[i]%MOD
    out%=MOD
  return out

ex=moddot(b, y)
print(ex)

Solution (Python):
def main():
    from itertools import accumulate

    MOD = 10 ** 9 + 7
    n = int(input())
    *x, = map(int, input().split())
    y = [b - a for b, a in zip(x[1:], x)]

    csum_invs = [0] + list(accumulate([pow(i, MOD - 2, MOD) for i in range(1, n + 1)]))
    
    
    
    
    
    

    fact = [0]
    t = 1
    for i in range(1, n + 1):
        t *= i
        t %= MOD
        fact.append(t)

    ret = 0
    for j, y_ in enumerate(y, 1):
        ret = (ret + csum_invs[j] * y_) % MOD
    print((ret * fact[n - 1]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
import math

n = int(input())
x = list(map(int,input().split()))

mod = 10**9 + 7

f = math.factorial(n-1)
f %= mod

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

l = []
for i in range(n-1):
    d = x[i+1] - x[i]
    l.append(d)



count = 0
k = f
plus = 0
for i in range(1,n):
    
    k = f + plus
    count += l[i-1] * k
    plus += f * modinv(i+1,mod)

print(int(count)%mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
X = np.array(read().split(),np.int64)

def cumprod(A, MOD = MOD):
    L = len(A); Lsq = int(L**.5+1)
    A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        A[:,n] *= A[:,n-1]; A[:,n] %= MOD
    for n in range(1,Lsq):
        A[n] *= A[n-1,-1]; A[n] %= MOD
    return A.ravel()[:L]
def make_fact(U, MOD = MOD):
    x = np.arange(U, dtype = np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact,fact_inv

U = 10 ** 5 + 5
fact, fact_inv = make_fact(U)

inv = np.zeros(U,np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD

coef = inv[1:N].cumsum() % MOD

answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]; answer %= MOD

print(answer)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
    
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

L = [1]*N
for i in range(1, N):
    L[i] *= L[i-1]*i
    L[i] %= mod
    
ans = 0
for i in range(1, N):
    ans += cmb(N-1, N-i, mod)*L[i-1]*L[N-i-1]*(A[N-1]-A[i-1])
    ans %= mod
        
L2 = [0]*(N-1)
for i in range(N-1):
    L2[i] = A[i+1]-A[i]

S = [0]*N
for i in range(N-1):
    S[i+1] = S[i] + L2[i]
    
L3 = [0]*N
for i in range(1, N):
    if N-i-1 >= i:
        L3[i] = L3[i-1] + S[N-i-1] - S[i-1]
    else:
        L3[i] = L3[N-i-1]

for t in range(1, N-1):
    ans += cmb(N-1, t+1, mod)*L[N-t-2]*L[t-1]*L3[t]
    ans %= mod
        
print(ans)