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



Sample input:
3
1 2 3


Sample output:
5

Submission status: Accepted

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class Comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]
cb = Comb(100005)

n = int(input())
a = list(map(int, input().split()))
a = [0] + a

from itertools import accumulate
a2 = list(accumulate(a))

ans = mint(0)
for m in range(1,n-1):
    sumdist = a2[n-1]-a2[n-1-m]-a2[m]
    ans += cb.fact[n-1]/(m)/(m+1)*sumdist
    sumdist = a[-1]-a[-1-m]
    ans += cb.fact[n-1]/(m)*sumdist

sumdist = a[-1]-a[1]
ans += cb.fact[n-2]*sumdist

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    x=LI()
    
    #区間を固定して考える．i番目の区間に対して，i番目のスライムが通過する確率は1
    #i-1番目のスライムの確率は1/2，i-2番目のスライムは1/3...
    
    diff=[0]*(N-1)
    for i in range(N-1):
        diff[i]=x[i+1]-x[i]
    
    p1=[1]*N
    for i in range(N-1):
        p1[i+1]=(p1[i]*(i+1))%mod#1から順にNまでかける
        
    a=[0]*N
    for i in range(N):
        #　a[i]は　mod下での　1/(i+1)
        a[i]=pow(i+1,mod-2,mod)
        
        
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+a[i])%mod
        
    ans=0
    for i in range(N-1):
        ans=(ans+S[i+1]*diff[i]*p1[-1])%mod
        
    print(ans)
    
    
    
    

main()

Submission status: Accepted

Solution code:
from itertools import accumulate
mod = 10 ** 9 + 7

N = int(input())
X = tuple(map(int, input().split()))
DX = [xr - xl for xl, xr in zip(X[:-1], X[1:])]

from1 = [1]
fromN = [1]
for i in range(1, N):
    from1.append(from1[-1] * i % mod)  # 1, 1*2, 1*2*3,...
    fromN.append(fromN[-1] * (N - i) % mod)  # 4, 4*3, 4*3*2, ...
fromN.reverse()

cnt = []
for a, b in zip(fromN[1:], from1[:-1]):
    cnt.append(a * b % mod)
cnt = list(accumulate(cnt))

ans = 0
for dx, c in zip(DX, cnt):
    ans = (ans + dx * c) % mod
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x=list(map(int,input().split()))
mod=10**9+7
inv=[0,1]
for i in range(2,n+1):
  inv+=[inv[mod%i]*(mod-int(mod/i))%mod]
l=[]
z=1
for i in range(1,n):
  z*=i
  z%=mod
l2=[z for i in range(n-1)]
for i in range(n-1):
  l.append(x[i+1]-x[i])
for i in range(n-1):
  l2[i]*=inv[i+1]
  l2[i]%=mod
l3=[]
l3.append(l2[0])
for i in range(n-2):
  l3.append(l3[-1]+l2[i+1])
ans=0
for i in range(n-1):
  ans+=l3[i]*l[i]
  ans%=mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, *L = map(int, open(0).read().split())
MOD = 10**9+7
D = [L[i+1]-L[i] for i in range(N-1)]
f = [1]
for i in range(1,N+1):
  f.append(f[-1]*i%MOD)
C = [1]
for i in range(1,N-1):
  C.append((C[-1]+pow(i+1,MOD-2,MOD))%MOD)
ans = sum(d*c for d,c in zip(D,C))%MOD
print(ans*f[N-1]%MOD)

Submission status: Accepted

Solution code:
N, *L = map(int, open(0).read().split())
MOD = 10**9+7
D = [b-a for a,b in zip(L,L[1:])]
f = [1]
for i in range(1,N+1):
  f.append(f[-1]*i%MOD)
C = [1]
for i in range(1,N-1):
  C.append((C[-1]+pow(i+1,MOD-2,MOD))%MOD)
ans = sum(d*c for d,c in zip(D,C))%MOD
print(ans*f[N-1]%MOD)

Submission status: Accepted

Solution code:
import sys
from math import factorial

rl = sys.stdin.readline


def mod_div(x, y, mod=10 ** 9 + 7):
    return x * pow(y, mod - 2, mod) % mod


def solve():
    N = int(rl())
    x = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    acc = [0] * N
    k = factorial(N - 1)
    for i in range(1, N):
        acc[i] = (acc[i - 1] + k) % MOD
        k = k * mod_div(i, i + 1) % MOD
    
    ans = 0
    for i in range(N - 1):
        ans = (ans + (x[i + 1] - x[i]) * acc[i + 1]) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N=int(input())
X=list(map(int,input().split()))
Y=[X[i+1]-X[i] for i in range(N-1)]
m=10**9+7
a,b=0,0
for i,y in enumerate(Y):
    b=(b+pow(i+1,m-2,m))%m
    a=(a+b*y)%m
f=1
for n in range(2,N):
    f=(f*n)%m
print(a*f%m)

Submission status: Accepted

Solution code:
n = int(input())
x = tuple(map(int,input().split()))

mod = 10**9 + 7
mul_l = [1] * (n+1)
mul_r = [1] * (n+1)
for i in range(1,n+1):
    mul_l[i] = mul_l[i-1] * i % mod

for i in range(n-1,-1, -1):
    mul_r[i] = mul_r[i+1] * i % mod

ans = 0
right = x[-1]
for i in range(n-1):
    tmp = right - x[i]
    tmp = tmp * mul_l[i] * mul_r[i+2] % mod
    ans = (ans + tmp)% mod

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x

frac = 1
for i in range(N - 1):
  frac *= i+1
  frac %= mod
T = 0
for i in range(N - 1):
  k = inved(i+1)
  T += (k * (A[N - 1] - A[i])) % mod
  T %= mod
print((T*frac)%mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

inv = ModInv(n, MOD)

#print(inv.inv)

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

ans = 0
temp = 0
for i in range(1, n):
    temp += inv.inv[i]
    ans += (x[i] - x[i-1]) * temp
    ans %= MOD

print((ans * b) % MOD)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i + 1] = self.factorial[i] * (i + 1) % mod
        self.inv[n] = pow(self.factorial[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def fact(self, m):
        return self.factorial[m]

    def invfact(self, m):
        return self.inv[m]


MOD = 10**9 + 7

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

D = [X[i + 1] - X[i] for i in range(N - 1)]

F = Factorial(N + 1, MOD)

res = 0
f = 0

for i in range(N - 1):
    f = (i + 1) * f + F.fact(i)
    f %= MOD
    res += D[i] * f * F.invfact(i + 1) * F.fact(N - 1)
    res %= MOD

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import copy

def main():
    N = int(input())
    x = list(map(int,input().split()))
    MOD = 10**9+7
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD

    cum = [0]
    for i in range(N):
        cum.append(cum[-1]+inv[i+1])

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
x = [int(x) for x in input().split()]
inf = 10**9+7
a = 1
for i in range(n-1, 0, -1):
    a *= i
    a %= inf
b = a
key = 0
ans = 0
for i in range(n-1):
    key += a*pow((i+1), inf-2, inf)
    key %= inf
    ans += key*(x[i+1]-x[i])
    ans %= inf
    

print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
x = list(map(int, input().split()))
kyori = [x[i + 1] - x[i] for i in range(N - 1)]
MOD = 10 ** 9 + 7
kai = [0] * (N + 1)
kai[0] = 1
for i in range(1, N + 1):
    kai[i] = (kai[i - 1] * i) % MOD
c = [0] * N
c[0] = 0
for i in range(1, N):
    c[i] = ((kai[N - 1] * pow(i, MOD - 2, MOD) % MOD) + c[i - 1]) % MOD
ans = 0
for i in range(N - 1):
    ans = (ans + kyori[i] * c[i + 1] % MOD) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = (ans*i)%M
    return ans

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

N = I()
x = LI()

nfact = fact(N-1)
pn = nfact
cumpn = nfact
ans = nfact*(x[1]-x[0])
for i in range(1,N-1):
    pn -= nfact*mod_inv(i)*mod_inv(i+1)
    pn %= mod
    cumpn += pn
    ans += cumpn*(x[i+1]-x[i])
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self //value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

class Combination:
    def __init__(self,max_n):
        self.max_n=0
        self.fact=[Fp(1)]
        self.ifact=[Fp(1)]
        self.make_fact_list(max_n)
    def C(self,n,k):return self.fact[n]*self.ifact[k]*self.ifact[n-k] if 0<=k<=n else 0
    def H(self,n,k):return self.C(n+k-1,k) if n or k else 1
    def P(self,n,k):return self.fact[n]*self.ifact[n-k] if 0<=k<=n else 0
    def make_fact_list(self,max_n):
        if max_n<=self.max_n: return
        self.fact+=[Fp(0)]*(max_n-self.max_n)
        self.ifact+=[Fp(0)]*(max_n-self.max_n)
        for i in range(self.max_n+1,max_n+1):
            self.fact[i]=self.fact[i-1]*i
            self.ifact[i]=self.ifact[i-1]//i
        self.max_n=max_n

def main():
    N,*X=map(int, open(0).read().split())
    f=Combination(N)
    ans=Fp(0)
    acc=Fp(0)
    for i,(x,y) in enumerate(zip(X,X[1:]),1):
        acc+=f.fact[N-1]//i
        ans+=acc*(y-x)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, 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

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

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]
print(answer % MOD)
# 35

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
acum=[1]
for i in range(2,n+1):
  tmp=acum[-1]+pow(i,mod-2,mod)
  tmp%=mod
  acum.append(tmp)
ans=0
for i in range(n-1):
  ans+=(arr[i+1]-arr[i])*acum[i]
  ans%=mod
for i in range(1,n):
  ans*=i
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
acum=[0]
for i in range(1,n+1):
  tmp=acum[-1]+pow(i,mod-2,mod)*pow(i+1,mod-2,mod)
  tmp%=mod
  acum.append(tmp)
ans=0
for i in range(n-1):
  ans+=arr[i]*acum[i]
  ans%=mod
  ans-=arr[i]*acum[n-2-i]
  ans%=mod
  ans-=arr[i]*pow(n-1-i,mod-2,mod)
  ans%=mod
for i in range(1,n):
  ans+=arr[-1]*pow(i,mod-2,mod)
  ans%=mod
for i in range(1,n):
  ans*=i
  ans%=mod
print(ans)

Submission status: Accepted

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

def make_mod_inv(l,p): # lまでの逆元を作る
    mod_inv = [0, 1] + [0] * (l+3) # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる
    for i in range(2, l+5):
        mod_inv[i] = -mod_inv[p % i] * (p // i) % p
    return mod_inv

mod_inv = make_mod_inv(n-1,MOD)

ans = 0

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

p = [0]*(n-1)
p[0] = 1 * factorial%MOD

for i in range(1,n-1):
    p[i] = p[i-1] + factorial*mod_inv[i+1]
    p[i] %= MOD

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

print(int(ans))

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
N=int(input())
X=list(map(int,input().split()))
lastX=X.pop()
mod=10**9+7
ferumaC=10**5+1
fac=[1,1]
for i in range(2,ferumaC):
    fac.append(fac[i-1]*i%mod)
ipow=[pow(i,mod-2,mod) for i in range(ferumaC+1)]

ruiipow=[0,ipow[2]*ipow[1]%mod]

for i in range(2,ferumaC):
    ruiipow.append((ruiipow[i-1]+ipow[i+1]*ipow[i])%mod)

count=0
"""for i in range(1,len(X)):
    count2=0
    for n in range(min(i,len(X)-i)):
        a=((len(X)-1)//i)*i+n
        if a>len(X)-1:
            a-=i
        #print(n,a,i)
        count2+=X[a]-X[n]
    count=(count+ipow[i+1]*ipow[i]*count2)%mod"""
for i in range(len(X)):

    count=(count+(ruiipow[i]-ruiipow[len(X)-i-1])*X[i])%mod
    #print(i,count*fac[N-1]%mod)

for i in range(len(X)):
    count=(count+(lastX-X[i])*ipow[len(X)-i])%mod
count=count*fac[N-1]%mod
print(count)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

ans = 0
mul = 0
for i in range(N-1):
    mul += pow(i+1, MOD-2, MOD)
    ans += (x[i+1] - x[i]) * mul % MOD
    ans %= MOD
for i in range(2, N):
    ans *= i
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)
input = lambda : sys.stdin.readline().rstrip()

def pow_mod(x, y, mod):
    tmp = x
    ret = 1
    while y > 0:
        if y % 2 == 1:
            ret = ret * tmp % mod
        tmp = tmp * tmp % mod
        y //= 2
    return ret

def inverse(x, mod):
    return pow_mod(x, mod - 2, mod)

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

MOD = 1000000007

def factorial(x):
    if x <= 1:
        return 1
    else:
        return x * factorial(x - 1) % MOD

f = factorial(N - 1)

h = [0]
for _ in range(N):
    h.append((h[-1] + f * inverse(len(h), MOD)) % MOD)

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int,input().split()))
Y = [b-a for a,b in zip(X,X[1:])]

MOD = 10**9+7
MAXN = N+5
fac = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD

ans = m = 0
for i,y in enumerate(Y):
    m += fac[N-1] * inv[i+1]
    ans += y*m
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
N = int(input())
A = [1 for _ in range(N)]
for i in range(2,N):
    A[i] = (i*A[i-1])%p
X = list(map(int,input().split()))
X.insert(0,0)
cnt = 0
for i in range(1,N):
    cnt = (cnt+((X[N]-X[i])*pow(i,p-2))%p)%p
print((cnt*A[N-1])%p)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
F = [1]*(n+1)
for i in range(n):
  F[i+1] = F[i]*(i+1)
  F[i+1] %= MOD
X = list(map(int, input().split()))
D = [X[i+1]-X[i] for i in range(n-1)]
T = [1]*n
for i in range(2, n):
  T[i] = T[i-1]*i+F[i-1]
  T[i] %= MOD
t = 1
for i in range(1, n-1):
  t *= (n-i)
  t %= MOD
  T[n-1-i] *= t
  T[n-1-i] %= MOD
ans = 0
for i in range(1, n):
  ans += D[i-1]*T[i]
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

M = 10 ** 9 + 7

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

x = np.diff(x)

# (N-1)!を求める
fac = 1
for i in range(1, N):
    fac = fac * i % M

c = [0] * N

for i in range(1, N):
    c[i] = (fac * pow(i, M - 2, M) % M) + c[i - 1] % M

# print(c)

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
*X, = map(int,input().split())

mod = 10**9+7

ans = 0
f = 1
for i in range(2,N):
    f *= i
    f %= mod
cnt = 0
for i,x in enumerate(X[:-1],1):
    tmp = f * pow(i,mod-2,mod)
    cnt += tmp
    cnt %= mod
    ans -= tmp*x
    ans %= mod
ans += cnt*X[-1]%mod
ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
x = [int(item) for item in input().split()]
inv = [0] * (n + 10)

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

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

ans = 0
for i, (x1, x2) in enumerate(zip(x, x[1:])):
    ans += (x2 - x1) * inv_cumsum[i+1] * n_minus_1_fac % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def modinv(a):
    return pow(a, MOD-2, MOD)


def main():
    N = I()
    x = LI()
    distance = [(x[i] - x[i-1]) % MOD for i in range(1, N)]

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

    c = [0] * (N - 1)
    for i in range(N-1):
        if i == 0:
            c[i] = (F * 1) % MOD
        else:
            c[i] = (F * modinv(i+1)) % MOD + c[i-1]

    moves = [(d * e) % MOD for d, e in zip(distance, c)]
    print(sum(moves) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
d = list( map(int, input().split() ) )
kai = 1
mod = 10**9+7
result = 0

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

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

for i in range(N-1):    
    result += ( kai * (d[N-1] - d[i]) * modinv(i+1) ) % mod 

print( result%mod )

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

# 1~nまでの逆元(mod m) O(n)
def mod_inv_list(n:int, m:int):
    # inv_t[i]: iの法mの下での逆元
    inv_t = [0] + [1]
    for i in range(2,n):
        inv_t += [inv_t[m % i] * (m - m//i) % m]
    return inv_t

def main():
    N = int(input())
    x = [int(i) for i in input().split()]
    MOD = 10**9 + 7

    inv_acum = mod_inv_list(N,MOD)
    for i in range(1,N):
        inv_acum[i] = (inv_acum[i] + inv_acum[i-1]) % MOD

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

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

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
p = pow(10,9) + 7

factorials = [1] + list(accumulate(range(1,n + 1), lambda x, y: (x * y) % p))

combinations = dict()
def combination(i, j):
    j = min(j, i - j)
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n = n >> 1
    return res

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    i_inv = modpow(i, p-2, p)
    t = factorials[n] * i_inv
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))

Submission status: Accepted

Solution code:
import numpy as np
M = 10**9+7
N = int(input())
X = np.array(list(map(int,input().split())),dtype='int64')

D = X[1:]-X[:N-1]

ans = 0
s = 0
nn = 1
for n in range(1,N):
    nn *= n
    nn %= M

for i,d in enumerate(D):
    s = (s + pow((i+1),M-2,M))%M
    ns = (nn*s) % M
    ans = (ans + ns*d %M ) % M

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
M = 10**9+7
N = int(input())
X = np.array(list(map(int,input().split())))

D = X[1:]-X[:N-1]

ans = 0
s = 0
nn = 1
for n in range(1,N):
    nn *= n
    nn %= M

for i,d in enumerate(D):
    s = (s + pow((i+1),M-2,M))%M
    ns = (nn*s) % M
    ans = (ans + ns*d %M ) % M
    ans %= M

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = int(input())
x = list(map(int,input().split()))
def mod_pow(x,n,mod):
    res = 1
    while(n > 0):
        if n&1:
            res = res * x % mod
        x = x * x % mod
        n >>= 1
    return res
prob = []
a = 0
for i in range(1,N):
    a += mod_pow(i,MOD-2,MOD)
    #koko
    a %= MOD
    prob.append(a)
ans = 0
for i in range(1,N):

    """for j in range(1,i+1):
        prob += 1/j
    """
    ans += (x[i]-x[i-1]) * prob[i-1]
    ans %= MOD

for i in range(1,N):
    ans *= i
    ans %= MOD
ans = int(ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
x = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

fac = 1

for i in range(2, N) :
  fac = fac * i % mod

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

ret = 0
for i in range(N - 1) :
  d = x[i + 1] - x[i]
  ret += d * inv_sum[i] % mod
  ret %= mod

print(ret * fac % mod)

Submission status: Accepted

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

def mod_pow(x, n, mod):
	res = 1
	while n > 0 : 
		if n&1 : 
			res = res * x % mod
		x = x * x % mod
		n >>= 1
	return res

prob = []
a = 0
for i in range(1, N):
	a += mod_pow(i, MOD-2, MOD)
	a %= MOD
	prob.append(a)
ans = 0
for i in range(1, N):
	ans += prob[i-1] * (x[i] - x[i-1])
	ans %= MOD
for i in range(1, N):
	ans = ans * i % MOD
print(ans)

Submission status: Accepted

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

def mod_pow(x, n, mod):
	res = 1
	while n > 0 : 
		if n&1 : 
			res = res * x % mod
		x = x * x % mod
		n >>= 1
	return res

ans = 0

prob = []
a = 0
for i in range(1, N):
	a += mod_pow(i, MOD-2, MOD)
	a %= MOD
	prob.append(a)
for i in range(1, N):
	ans += prob[i-1] * (x[i] - x[i-1])
	ans %= MOD

#factor = 0

#for i in range(1, N):
#	factor += mod_pow(i, MOD-2, MOD)
#	factor %= MOD
#	ans += factor * (x[i] - x[i-1])
#	ans %= MOD

for i in range(1, N):
	ans = ans * i % MOD
print(ans)

Submission status: Accepted

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

def mod_pow(x, n, mod):
	res = 1
	while n > 0 : 
		if n&1 : 
			res = res * x % mod
		x = x * x % mod
		n >>= 1
	return res

ans = 0
factor = 0

for i in range(1, N):
	factor += mod_pow(i, MOD-2, MOD)
	factor %= MOD
	ans += factor * (x[i] - x[i-1])
	ans %= MOD
for i in range(1, N):
	ans = ans * i % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def inv(x):
    return pow(x, MOD-2, MOD)

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

fact = [1]

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

inv_table = [-1]*(N+1)

for i in range(N+1):
    inv_table[i] = inv(i)

inv_acc = [0]

for inv_i in inv_table:
    inv_acc.append(inv_acc[-1]+inv_i)
    
for i in range(N-1):
    ans += (x[i+1]-x[i])*(inv_acc[i+2]-inv_acc[1])
    ans %= MOD

ans *= fact[N-1]
ans %= MOD

print(ans)