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:
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)]))
    # csum_invs = [0]
    # t = 0
    # for i in range(1, n + 1):
    #     t += pow(i, MOD - 2, MOD)
    #     t %= MOD
    #     csum_invs.append(t)

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

Submission status: Accepted

Solution code:
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)

# print(l)

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

print(int(count)%mod)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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


fac = [1]


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


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

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

print(res % mod)

Submission status: Accepted

Solution code:
#coding:utf-8
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)
    # def calc(k,slimes):
    #     # print(slimes)
    #     if k == N-1:
    #         return 0
    #     r = 0
    #     # for i in range(N-k-1):
    #     #     slimes2 = slimes[:]
    #     #     r = (slimes2[i+1]-slimes2[i]) / float(N-k-1)
    #     #     slimes2.pop(i)
    #     #     r += calc(k+1,slimes2) % MOD
    #     i = N-k-2
    #     slimes2 = slimes[:]
    #     print(i,slimes2)
    #     r = (slimes2[i+1]-slimes2[i]) * f / (N-k-1) % MOD
    #     slimes2.pop(i)
    #     r += calc(k+1,slimes2) 
    #     return r % MOD
    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()

Submission status: Accepted

Solution code:
mod = 10**9+7

# N = 15
N = int(input())
xx = list(map(int, input().split()))

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

aa = [a]
for i in range(N-2):
    aa.append((aa[-1]+a*pow(i+2,mod-2,mod))%mod)


dx = [xx[i]-xx[i-1] for i in range(1,N)]

ans = 0
for a,d in zip(aa,dx):
    ans += a*d
    ans %= mod

print(ans%mod)

Submission status: Accepted

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

bl = []

for i in range(n-1):
    bl.append(xl[i+1] - xl[i])

import itertools
bl_ac = list(itertools.accumulate(bl))

MOD = 10**9 + 7
N = 10**5

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

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

ans = 0
p = 1
c = 1
for i in range(n-1):
    ans += bl[i] * perm(n-1, n-2-i) * c
    ans %= MOD
    c *= i + 2
    c += p
    c %= MOD
    p *= i + 2
    p %= MOD

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int, input().split()))
d = []
for x1, x2 in zip(x, x[1:]):
    d.append(x2 - x1)
mod = 10 ** 9 + 7
base = 1

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

for i in range(1, n):
    base *= i
    base %= mod
ans = 0
b = base
for i, di in enumerate(d):
    ans += (base * di)  % mod
    ans %= mod
    base += b * inv_t[i+2]
    base % mod
print(ans)

Submission status: Accepted

Solution code:
# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

# factorial x!
def fact(x):
    global mod
    res=1
    for i in range(2,x+1):
        res=res*i%mod
    return res

# combination nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        return fact(n)*inv(fact(r))*inv(fact(n-r))%mod

mod=10**9+7

N=int(input())
x=[0]
x.extend(list(map(int,input().split())))
invs=[inv(d) for d in range(N)]
# print(invs)
ans=0;s=0
for d in range(1,(N-1)//2+1):
    s=(s+x[N-d]-x[d])%mod
    ans=(ans+s*invs[d]*invs[d+1])%mod
    if d!=N-d-1:
        ans=(ans+s*invs[N-d-1]*invs[N-d])%mod
for i in range(1,N):
    ans=(ans+(x[N]-x[i])*invs[N-i])%mod
ans=ans*fact(N-1)%mod

print(ans)

Submission status: Accepted

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

mod = 10**9+7

kukan_cnt = [0] * (N-1)

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

kukan_cnt[0] = orig

tmp = 1

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

for i in range(1,N):
	dist = X[i]-X[i-1]
	dist %= mod

	ans += dist*kukan_cnt[i-1]

	ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
n = input()    
m = n.split()
p = [int(i) for i in m]
list = 1
for i in range(N-1):
    list = (list * (i+1)) % 1000000007

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

A = 0
for i in range(N-1):
    if i == 0:
        A = (A + list * (p[N-1]-p[i])) % 1000000007
    else:
        A = (A + list * (p[N-1]-p[i]) * modinv(i+1,1000000007)) % 1000000007
print(A)

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())
slime = [ int(v) for v in input().split() ]
distance = [ slime[i+1] - slime[i] for i in range(n-1) ]

ans = 0
t = 1
for i in range(1, n):
    t *= i
    t %= mod

s = 0
for i in range(n-1):
    s += t * pow(i+1, mod-2, mod)
    s %= mod
    ans += s * distance[i]
    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,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
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 NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n=I()
x=LI()

cm=Comb(n+20)

StrN=[0]*(n+10)
StrN[1]=1
StrN[0]=0
def St(n):
    if n==1:
        return 1
    if StrN[n]!=0:
        return StrN[n]
    else:
        #a(n+1)=(n+1)*a(n)+n!
        StrN[n]=(n)*St(n-1)+cm.fac[n-1]
        StrN[n]%=mo
        return StrN[n]



St(n)

Pat=[0]*(n+1)
for i in range(n):
    Pat[i]=StrN[i]*cm.fac[n-1]*cm.inv[i]%mo
#show('Pat',Pat)
#show('St',StrN)

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

print(ans%mo)
#show(SSS)

Submission status: Accepted

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

MOD = 10**9 + 7
def inv(a):
	b = MOD
	u = 1
	v = 0
	while b > 0:
		t = a // b
		a -= t*b
		a,b = b,a
		u -= t*v
		u,v = v,u
	u %= MOD
	return u

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

ans = 0
bunshi = 1
bunbo = 1
for i in range(1, N):
	keisu = (facts[N-1] * bunshi * inv(bunbo)) % MOD
	ans = (ans + keisu * d[i-1]) % MOD
	bunshi = (bunshi * (i+1) + bunbo) % MOD
	bunbo = (bunbo * (i+1)) % MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse

    def div(self, x, y):
        """ MOD除算 """

        return x * pow(y, self.MOD-2, self.MOD) % self.MOD

N = INT()
A = LIST()
B = [0] + [A[i+1] - A[i] for i in range(N-1)]

mt = ModTools(N, MOD)
add = mt.fact[N-1]
cnt = [0] * N
for i in range(1, N):
    cnt[i] = round(cnt[i-1] + add)
    cnt[i] %= MOD
    add *= mt.div(i , (i+1))
    add %= MOD

ans = 0
for i in range(1, N):
    ans += B[i] * cnt[i]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
p = mod - 2
S = []
while p != 0:
  S = [p%2] + S[:]
  p //= 2
frac = 1
for i in range(N - 1):
  frac *= i+1
  frac %= mod
T = 0
for i in range(N - 1):
  k = 1
  for j in range(len(S)):
    if S[j] == 1:
      k *= i+1
      k %= mod
    if j != len(S) - 1:
      k *= k
      k %= mod
  T += (frac * k * (A[N - 1] - A[i])) % mod
  T %= mod
print(T%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
X = LI()
d = [0] * (n - 1)
for i in range(n - 1):
    d[i] = (X[i + 1] - X[i]) % mod



fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod



for i in range(1, n):
    inv[i] = pow(i, mod - 2, mod)




L = [fac[n - 1] * inv[i] % mod for i in range(1, n)]
for k in range(1, n - 1):
    L[k] = (L[k] + L[k - 1]) % mod




ret = 0
for j in range(n - 1):
    ret = (ret + L[j] * d[j] % mod) % mod


print(ret % mod)

Submission status: Accepted

Solution code:
from itertools import accumulate
MOD = 10 ** 9 + 7
N = int(input())
Xs = list(map(int, input().split()))
Ds = []
for i in range(1, N):
    Ds.append(Xs[i] - Xs[i-1])
S = list(accumulate(Xs))

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

def div(a, b):
    return a * pow(b, MOD-2, MOD)

ans = 0
prev = 0
fact = factorials[N-1]
for i, d in enumerate(Ds):
    n = i+1
    tmp = prev + div(fact, n)
    prev = tmp
    ans += tmp * Ds[i]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
n_ = n + 3
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
revs = [rev[i+1]*fun[i] for i in range(n_)]
for i in range(n_-1):
  revs[i+1] = (revs[i+1] + revs[i])%mod
ans = 0
for i in range(n-1):
  ans += (l[i+1]-l[i])*revs[i]
  ans %= mod
print(ans*fun[n-1]%mod)

Submission status: Accepted

Solution code:

N = int(input())

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

mod = 10 ** 9 + 7


ans = 0
t = [1]
u = [1]

for i in range(N):

    i += 1
    t.append(t[-1] * i % mod)

for i in range(N-1):
    u.append(u[-1] * (N-1-i) % mod)
    
#print (t)
#print (u)
u.reverse()


now = 0
for i in range(N-1):

    now += u[i+1] * t[i]
    now %= mod
    ans += now * (x[i+1] - x[i])
    ans %= mod
    #print (i,ans/6)

print (ans)

Submission status: Accepted

Solution code:
n=int(input())
x=list(map(int,input().split()))
c=0
m=10**9+7
q=[1,1]
p=[1,1]
an=0
for j in range(1,n+1):
    q.append((q[-1]*j)%m)
    p.append((p[-1]*(n-j))%m)
for i in range(1,n):
    c=(c*i+q[i])%m
    an=(an+(x[i]-x[i-1])*c*p[n-i])%m
print(an)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md=10**9+7
    n=II()
    xx=LI()
    fac=[1]*n
    for k in range(1,n):
        fac[k]=fac[k-1]*k%md
    rfac=[n-1]*n
    for k in range(n-2,-1,-1):
        rfac[k]=rfac[k+1]*k%md
    ans=0
    coff=0
    for i,(x0,x1) in enumerate(zip(xx,xx[1:]),1):
        d=x1-x0
        if i+1<n:coff+=fac[i-1]*rfac[i+1]
        else:coff+=fac[i-1]
        #print(coff)
        ans+=d*coff
        ans%=md
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)


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


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1) % mod


mod = 10**9+7
N = int(input())
x = [0] + list(map(int, input().split()))
fact = factorial(N-1)

ans = 0
for k in range(2, N):
    ans = (ans + x[k] * (1 - mod_inverse(k)))

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

ans = ans * fact % mod

ans = (ans + fact * sum((x[N] - x[k]) * mod_inverse(N-k) for k in range(1, N))) % mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10 ** 9 + 7
a = list(map(int,input().split()))
b = []
for i in range(1,n):
  b.append(a[i]-a[i-1])
c = [1]
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
#print(inv(5))
#print(inv(2))
for i in range(2,n):
  c.append((c[-1]+inv(i))%mod)
#print(c)
ans = 0
for i in range(n-1):
  ans += c[i] * b[i]
  ans %= mod
fact = 1
for i in range(1,n):
  fact *= i
  fact %= mod
ans *= fact
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def perm(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * self.finv[n-k] % self.mod % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 10**9+7
P = PERM_COMB_MOD(2*10**5, mod=mod)

n = int(input())
x = list(map(int, input().split()))
base = x[-1]-x[0]
left = []
k = n-1
for i in range(k):
    a = P.perm(k, k-(i+1))*P.fac[i]
    left.append(a)
left[0] = 0
for i in range(1, k):
    left[i] += left[i-1]

ans = base*P.fac[k]
for i in range(1, n-1):
    tmp = x[i+1]-x[i]
    ans += tmp*left[i]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
x = list(map(int,input().split()))

#n = 10**5
#x = list(range(10**5))
mod = 10**9 + 7

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

dp = [0] * (n-1)
dp2 = [0] * (n-1)
dp3 = [0] * n
dp3[0] = 1

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

dp[0] = x[1] - x[0]
dp2[0] = 1

for i in range(n-2):
    dp2[i+1] = dp2[i] * (i+2) + dp3[i]
    dp2[i+1] %= mod
ans = 0
for i in range(n-2):
    dp[i+1] = dp[i] * (i+2) + (x[i+2] - x[i+1]) * dp2[i+1]
    dp[i+1] %= mod

print(dp[-1] % mod)

Submission status: Accepted

Solution code:

n = int(input())

A = list(map(int,input().split()))

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

mod  =10**9+7

B = [0] * (n+1)


l=n+5
M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def inv(x, y):  # xのmod yでの逆元を返す関数
    yy = y - 2
    ans = 1
    while yy > 0:
        if yy % 2 == 1:
            ans = (ans * x) % y
        x = (x**2) % y
        yy //= 2
    return ans

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


p=M[n]
ans = p*A[0]
for i in range(1, n):
    
    p = (p + M[n-1] + B[i+1]*(n-1-i)) % mod
    # print("p",p)
    ans = (ans+p*A[i]) % mod
print(ans%mod)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	X = getlist()

	#例外
	if N == 2:
		print(X[1] - X[0])
		return

	#前処理
	ans = 0
	left = [1] * (N - 1)
	right = [N - 1] * (N - 1)
	for i in range(N - 2):
		left[i + 1] = (left[i] * (i + 2)) % con
		right[N - 3 - i] = (right[N - 2 - i] * (N - 2 - i)) % con

	# print(left)
	# print(right)

	fig = [0] * (N - 1)
	fig[0] = left[N - 2]
	for i in range(1, N - 2):
		fig[i] = (left[i - 1] * right[i + 1]) % con
	fig[N - 2] = left[N - 3] #チェック

	# print(fig)

	figsum = [0] * (N - 1)
	figsum[0] = fig[0]
	for i in range(N - 2):
		figsum[i + 1] = (figsum[i] + fig[i + 1]) % con

	# print(figsum)

	for i in range(N - 1):
		dist = X[i + 1] - X[i]
		val = figsum[i]
		ans += dist * val
		
	ans %= con
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
mod=1000000007
n=int(input())
X=list(map(int,input().split()))
L=[]
for  i in range(n-1):
    L.append(X[i+1]-X[i])
for i in range(n-2,0,-1):
    L[i-1]=(L[i-1]+L[i])%mod
l=[1]
for i in range(n-1):
    l.append(l[-1]*(i+1)%mod)
ll=[1]
for i in range(n-1,0,-1):
    ll.append(ll[-1]*i%mod)
ans=0
for i in range(n-1):
    ans=(ans+((L[i]*l[i])%mod)*ll[n-2-i])%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
x_list=list(map(int,input().split()))
INF=10**9+7
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=0
s=1
for i in range(n-1):
    s=s*(i+1)
    s=s%INF
for i in range(n-1):
    x=modinv(i+1,INF)
    ans=(ans+s*x*(x_list[n-1]-x_list[n-2-i]))%INF
sumx=[]
isumx=[]
sx=0
isx=0
for i in range(n-1):
    sx=(sx+x_list[i])%INF
    isx=(isx+x_list[n-2-i])%INF
    sumx.append(sx)
    isumx.append(isx)
for i in range(n-2):
    x=modinv(i+1,INF)
    y=modinv(i+2,INF)
    ans=(ans+s*x*y*(isumx[i]-sumx[i]))%INF
print(ans)

Submission status: Accepted

Solution code:
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):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
    
n=int(input())
x=list(map(int,input().split()))
mod=10**9+7
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]*=mod_inv((i+1),mod)
  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:
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m


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

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

s=0
ans=0
for i in range(1,n):
    l=x[i]-x[i-1]
    s=s+P*modinv(i,MOD)
    s%MOD
    ans+=l*s
    ans%=MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
x = list(map(int, input().split()))
dp = [[0] for _ in range(N)]
dp[0] = 0
f = 1
fact = [1]*N
for i in range(1, N):
    dp[i] = dp[i-1]*i+f
    dp[i]%=mod
    f*=i
    f%=mod
fact[-1] = 1
for i in range(N-1)[::-1]:
    fact[i] = fact[i+1]*(i+1)
    fact[i]%=mod
ans = 0
for i in range(N-1):
    ans+=dp[i+1]*fact[i+1]*(x[i+1]-x[i])%mod
    ans%=mod
print(ans)