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:
class Combination:
    def __init__(self, n_max=10**6, mod=10**9+7):
        # self._n_max = n_max
        self._fac, self._finv, self._inv = [0]*n_max, [0]*n_max, [0]*n_max
        self._fac[0], self._fac[1] = 1, 1
        self._finv[0], self._finv[1] = 1, 1
        self._inv[1] = 1
        self._mod = mod
        for i in range(2, n_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 com(self, n, r):
        if n < r: return 0
        if n < 0 or r < 0: return 0
        return self._fac[n] * (self._finv[r] * self._finv[n - r] % self._mod) % self._mod

    def perm(self,n,r):
        if n < r: return 0
        if n < 0 or r < 0: return 0
        return self._fac[n] * (self._finv[n-r] % self._mod) % self._mod


n = int(input())
xl = list(map(int, input().split()))
com = Combination(10**5+1)
MOD = 10**9+7

# print(com.perm(0,0),com.perm(1,1))

csum = 0
ans = 0
for i in range(n-1):
    diff = xl[i+1]-xl[i]
    val = com.com(n-1,i+1)*com.perm(i,i)*com.perm(n-2-i,n-2-i)
    # print(val,'-')
    csum += val
    csum %= MOD
    ans += diff*csum
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9+7
    ans = 0
    fact = 1
    for i in range(2, n):
        fact = fact*i % mod

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

    for i in range(n-1):
        ans = (ans + (a[i+1]-a[i])*fact_2[i]) % mod
    print(ans % mod)


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    x = [int(i) for i in ipt().split()]
    d = [x[i+1]-x[i] for i in range(n-1)]
    k = [1]
    for i in range(1,n):
        k.append(k[-1]*i%mod)

    #n!の逆元を求める
    g2 = [1,1]
    inverse = [0,1] #逆元テーブル計算用テーブル
    for i in range(2,n+1):
        inverse.append((-inverse[mod%i]*(mod//i))%mod)
        g2.append((g2[-1]*inverse[-1])%mod)

    ans = 0
    na = 0
    for i in range(1,n):
        na = na*i+k[i-1]
        na %= mod
        ans += na*d[i-1]*k[-1]*g2[i]
        ans %= mod

    print(ans)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

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

fac,finv,inv=facinv(N)

Inv=0
ans=0
for k in range(N-1):
    Inv=Inv+inv[k+1]
    res=Inv*(x[k+1]-x[k])
    ans=(ans+res)%MOD
print(ans*fac[N-1]%MOD)

Submission status: Accepted

Solution code:
def examA():
    N = I()
    S = [""]*N; T = [""]*N
    for i in range(N):
        S[i],T[i] = LSI()
        T[i] = int(T[i])
    X = SI()
    ans = 0
    flag = False
    for i in range(N):
        if flag:
            ans +=T[i]
        if S[i]==X:
            flag = True
    print(ans)
    return

class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

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

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

def examB():
    N = I()
    X = LI()
    B = [1]*N
    for i in range(1,N-1):
        B[i+1] =B[i]*(i+1)
        B[i+1] %= mod
    XL = [X[i+1]-X[i] for i in range(N-1)]
    C = combination(N, mod)
    """
        cumL = [0]*N
    cumL[1] = XL[0]
    for i in range(1,N):
        cumL[i+1] = cumL[i]+XL[i]
    print(cumL)
    """
    ans = 0; cur = B[-1]
    now = 0
#    print(B,XL)
    for i in range(N-1):
        ans += cur*XL[i]
        ans %=mod
#        print(ans)
    for i in range(1,N-1):
        now += C.comb(N-1,1+i,mod)
        ans += now*XL[i]
        ans %=mod
#        print(ans)
    print(ans)
    return
"""
4
1 3 6 7
"""
def examB2():
    N = I()
    X = LI()
    L = [0]*(N-1)
    for i in range(N-1):
        L[i] = X[i+1] - X[i]

    S = [1]*N
    for i in range(1,N):
        S[i] = S[i-1] + pow(i+1,mod-2,mod)
    C = combination(N,mod)
    cnt = 0
    for i in range(N-1):
        #print(S[i], L[i], C.fac[N - 1])
        cnt += S[i]*L[i]*C.fac[N-1]%mod
        cnt %= mod
    ans = cnt
    print(ans)
    return

def examC():

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB2()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N = int(readline())
    X = list(map(int, readline().split()))

    mul_mod = [0] * N

    cur = 1
    for i in range(1, N):
        cur *= i
        cur %= MOD
    mul_mod[1] = cur

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

    p = [0] * (N - 1)
    p[-1] = sum(mul_mod[1:N]) % MOD

    for i in range(2, N):
        p[-i] = p[-i + 1] - mul_mod[N - i + 1]
        p[-i] %= MOD

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

N = 10**6
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 )

kaijo=1
for i in range(n-1):
    kaijo*=n-i-1
    kaijo%=mod
# print(kaijo)

ans=0
cnt=0
for i in range(n-1):
    y1,y2=x[i],x[i+1]
    sa=y2-y1
    cnt+=g1[n-1]*g2[i+1]*g1[i]
    ans+=cnt*sa
    # print(g1[n-1]*g2[i+1]*g1[i])
    ans%=mod
    # print(ans)
# print(g1[:10])
# print(g2[:10])
print(ans)

Submission status: Accepted

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

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
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
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)
ans=0
for i in range(n-1):
  ans+=(x[n-1]-x[i])*g1[n-1]*pow(i+1,mod-2,mod)
  ans%=mod
print(ans)

Submission status: Accepted

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

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

answer_bunshi=0
answer_bumbo=1
inv_bunshi=0
inv_bumbo=1
for i in range(1,N):  
  inv_bunshi=(i*inv_bunshi+inv_bumbo)%MOD
  inv_bumbo=(inv_bumbo*i)%MOD
  #print(inv_bunshi,inv_bumbo)
  
  xdiff=xlist[i]-xlist[i-1]
  term_bunshi=(xdiff*inv_bunshi)%MOD
  answer_bunshi=(answer_bunshi*inv_bumbo+term_bunshi*answer_bumbo)%MOD
  answer_bumbo=(answer_bumbo*inv_bumbo)%MOD
#print(answer_bunshi,answer_bumbo)

answer_bunshi=(answer_bunshi*fact_nm1)%MOD
answer=answer_bunshi*pow(answer_bumbo,MOD-2,MOD)
answer%=MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
x = list(map(int, input().split()))
M = 10**9+7
p = 1
invs = [None]
v = 1
for i in range(2, n+1):
    invs.append(v)
    v += pow(i, M-2, M)
    v %= M
for i in range(1, n):
    p *= i
    p %= M
ans = 0
for i in range(n-1):
    ans += (x[i+1]-x[i]) * invs[i+1]
    ans %= M
ans *= p
print(ans%M)

Submission status: Accepted

Solution code:
import itertools
mod = 10**9 + 7
stdin = [int(_) for _ in open(0).read().split()]
N, X = stdin[0], stdin[1:]
A = [pow(i, mod - 2, mod) for i in range(N)]
D = [0] + [a - b for a, b in zip(X[1:], X[:-1])]
f = 1
for i in range(1, N):
    f *= i
    f %= mod
A = [d * f * a % mod for d, a in zip(D, list(itertools.accumulate(A)))]
print(sum(A) % mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def MOD_perm(n, r):
    rtn = 1
    for _ in range(r):
        rtn *= n
        rtn %= MOD
        n -= 1
    return rtn

def MOD_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 = u % MOD
    if u < 0:
        u += MOD
    return u

def main():
    n = int(input())
    x = list(map(int, input().split()))
    ans = 0
    inv = 0
    perm = MOD_perm(n-1, n-1)
    for i in range(1, n):
        dif = x[i] - x[i-1]
        inv += MOD_inv(i)
        inv %= MOD
        ans += dif * perm * inv
        ans %= MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
n = int(input())
x = list(map(int, input().split()))
mod = 10 ** 9 + 7
c = 1
for i in range(2, n):
    c *= i
    c %= mod
c2 = deepcopy(c)
ans = 0
for i in range(n):
    ans += (x[i] - x[i - 1]) * c2
    ans %= mod
    c2 += pow(i + 1, mod - 2, mod) * c
    c2 %= mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

def factorial(n, mod):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
        fact %= mod
    return fact

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

ans *= fact
ans %= mod

print(ans)

Submission status: Accepted

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

ans = 0
for j in range(1,N-1):
    ans += x[j]*j*pow(j+1,mod-2,mod)
    ans %= mod
for i in range(N-2):
    ans += x[i]*(-N+i+2)*pow(N-i-1,mod-2,mod)
    ans %= mod
for i in range(N-1):
    ans += (x[N-1]-x[i])*pow(N-1-i,mod-2,mod)
    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

MAX = 2*10**5+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD
    
N = int(input())
x = list(map(int, input().split()))
ans = 0
acc = [0]

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

for i in range(N-1):
    d = x[i+1]-x[i]
    ans += d*acc[i+1]
    ans %= MOD
    """
    for j in range(i+1):
        ans += d*C(N-1, j+1)*fact[j]*fact[N-1-(j+1)]
        ans %= MOD
    """
print(ans)

Submission status: Accepted

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

delta = [X[i+1] - X[i] for i in range(n-1)]
mod = 10**9 + 7

mother = 1
for i in range(1,n):
    mother *= i
    if mother > mod:mother %= mod

total = 0
ans = 0
for i in range(n-1):
    now = (total*pow(i+1,mod-2,mod) + 1)%mod
    ans += now*delta[i]%mod
    if ans > mod: ans %= mod
    total += now
print(ans*mother%mod)

Submission status: Accepted

Solution code:
# Fusing Slimes
N = int(input())
X = list(map(int, input().split()))
mod = 10 ** 9 + 7
rev_sum=[0 for i in range(N+1)]
#rev_sum[x]= 1/1+   1/x
for i in range(1,N+1):
    rev_sum[i]+=rev_sum[i-1]+pow(i,mod-2,mod)
ans=0
for i in range(N-1):
    ans+=(X[i+1]-X[i])*rev_sum[i+1]
    ans%=mod
for i in range(1,N):
    ans=ans*i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

from itertools import accumulate

def mulmod(a, b):
    return a * b % MOD
    
from_left = list(accumulate(range(N-1, 1, -1), mulmod))[::-1] + [1]
from_right = [1] + list(accumulate(range(1, N-1), mulmod))
count = list(accumulate([mulmod(l, r) for l, r in zip(from_left, from_right)]))

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)


    class Combinatorics:
        def __init__(self, size: int, mod: int):
            '''
            >>> c = Combinatorics(size=10, mod=10**9+7)
            >>> c.fact
            [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
            >>> c.inv
            [1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206, 283194722]
            '''
            self.size =  size
            self.mod = mod
            self.fact = self._build_factorial(size, mod)
            self.inv = self._build_inv_factorial(size, mod)
        
        def _build_factorial(self, size:int , mod: int) -> None:
            '''
            fact_mod[i] は i! % mod を表すとする
            O(n) で fact_mod[size] まで計算結果がメモされたテーブルを構築して返す
            '''
            fact = [1] * (size + 1)
            for i in range(1, size + 1):
                fact[i] = (fact[i-1] * i) % mod
            return fact
        
        def _build_inv_factorial(self, size: int, mod: int) -> None:
            '''
            inv_fact_mod[i] は 1/i! % mod を表すとする
            O(n+lgm) で inv_fact_mod[size] まで計算結果がメモされたテーブルを構築して返す
            Note:
                [フェルマーの小定理]
                a ^ p-1 ≡ 1 (mod p)
                a ^ p-2 ≡ 1/a (mod p) (逆元)
                nCr = (n!) / ((n-r)! * r!) だが、mod p の世界ではこの分母を逆元を用いて計算しておくことが可能
            '''
            inv_fact_mod = [1] * (size + 1)
            inv_fact_mod[size] = pow(self.fact[size], mod-2, mod)    # a ^ p-2 ≡ 1/a (mod p) において a = n! とする。 1/n! (mod p) を求める
            for i in range(size-1, -1, -1):
                inv_fact_mod[i] = (inv_fact_mod[i+1] * (i+1)) % mod    # 1/(n-1)! = 1/n! * n
            return inv_fact_mod
        
        def comb(self, n: int, r: int) -> int:
            '''
            nCr % mod を O(1) で計算する。
            Examples:
                >>> c = Combinatorics(size=100, mod=10**9+7)
                >>> c.comb(100, 50)
                538992043   
            '''
            numerator = self.fact[n]
            denominator = (self.inv[n-r] * self.inv[r]) % self.mod
            return (numerator * denominator) % self.mod
    

    n = ii()
    L = lmi()

    c = Combinatorics(10**5, mod)
    seq = [(c.fact[n-1] * pow(i, mod-2, mod)) % mod for i in range(1, n)]
    ac = list(accumulate(seq))

    ans = 0
    for i in range(n-1):
        tmp = (L[i+1] - L[i]) * ac[i] % mod
        ans = (ans + tmp) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from itertools import accumulate
Q = 10**9+7

def getFactorials(N):
    ret = [0]*(N+1)
    ret[0] = 1
    for i in range(1, N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def getInv(N):
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

def getCmb(N):
    inv = getInv(N)
    nCr = [1] * (N + 1)
    for i in range(1, N + 1):
        nCr[i] = (nCr[i - 1] * (N - i + 1) * inv[i]) % Q
    return nCr


def main():
    N = int( input())
    X = list( map( int, input().split()))
    if N == 2:
        print(X[0])
        return
    factorials = getFactorials(N)
    combs = getCmb(N-1)
    accX = list( accumulate(X))
    # print(accX)
    ans = 0
    for i in range(N-1):
        z = X[N-1] - X[N-2-i]
        c = factorials[N-2-i]*combs[i+1]%Q*factorials[i]%Q
        ans += z*c%Q
        ans %= Q
        # print(i, "hashi", z, c, z*c)
        if i == N-2:
            continue
        x = (accX[N-1] - accX[i]) - (accX[N-2-i]) - z
        y = factorials[N-3-i]*combs[i+2]%Q*factorials[i]%Q
        # print(i, x, y)
        ans += x*y%Q
        ans %= Q
        # (N-k-1)!*C(N-1,k)*(k-2)!
    print(ans)
    
if __name__ == '__main__':
    main()

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)]
ans = 0
mod = 10 **9 + 7
fac = 1
for i in range(1, n):
    fac *= i
    fac %= mod

tmp = 0
for i in range(n-1):
    tmp += fac * pow(i+1, mod-2, mod)
    tmp %= mod

    ans += d[i] * tmp
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    ans = 0
    fact = [1]
    for i in range(1,N):
        fact.append(fact[-1]*i%MOD)
    inv_fact = [1] * N
    inv_fact[-1] = pow(fact[N - 1],MOD - 2,MOD)
    for i in range(N - 1,0,-1):
        inv_fact[i - 1] = inv_fact[i]*i%MOD
    
    cum = 0
    for i in range(N - 1):
        cum += fact[N - 1] * inv_fact[i + 1] * fact[i] % MOD
        cum %= MOD
        ans += cum * (X[i + 1] - X[i])
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)

N = int(input())
X = list(map(int, input().split()))
Acc = [X[-1] - X[i] for i in range(N - 2, -1, -1)]

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

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def M(n): return ModInt(n)

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

    def __str__(self):
        return str(self.n)

def main():
    n = I()
    xa = LI()

    m1 = M(1)
    c = [m1]
    for i in range(2, n+2):
        c.append(c[-1] + m1 / i)

    r = M(0)
    for i in range(1,n):
        t = xa[i] - xa[i-1]
        r += c[i-1] * t

    for i in range(n-1,1,-1):
        r *= i

    return r

print(main())

Submission status: Accepted

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

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
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

total = 0
min_sekisan = 1
mod = 10 ** 9 + 7
for i in range(1, n):
    min_sekisan *= i
    min_sekisan %= mod
#print(min_sekisan)

counter = 0
for i in range(n-1):
    counter += min_sekisan
    total -= (min_sekisan * X[i]) % mod
    min_sekisan *= i + 1
    min_sekisan *= mod_inv(i + 2, mod)
    min_sekisan %= mod
total += (X[n-1] * counter) % mod
print(total % mod)

"""
from collections import defaultdict as dd
import copy
def count(n):
    lis = [[[i for i in range(1, n + 1)], dd(int)]]
    while len(lis[0][0]) != 1:
        temp = []
        for nums, counter in lis:
            for i in range(len(nums)-1):
                new_dic = copy.deepcopy(counter)
                new_dic[nums[i]] -= 1
                new_dic[nums[i+1]] += 1
                temp.append([nums[:i] + nums[i+1:], new_dic])
        lis = temp
    return lis
#print(count(4))
#print(len(count(4)))

total = dd(int)
for lis, dic in count(7):
    for key, val in dic.items():
        total[key] += val
print(total)
"""

Submission status: Accepted

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

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

va, vb = 0, 1
ans = 0

for i in range(N-1):
    d = x[i+1]-x[i]
    va = ((i+1)*va+vb)%MOD
    vb = ((i+1)*vb)%MOD
    ans += (d*va*pow(vb, MOD-2, MOD)*m)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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

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

va, vb = 0, 1
ans = 0

for i in range(N-1):
    d = x[i+1]-x[i]
    va = ((i+1)*va+vb)%MOD
    vb = ((i+1)*vb)%MOD
    ans += (d*va*pow(vb, MOD-2, MOD)*m)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

def inv_mod(n,mod):
    inv_mod = [0]*(n+1)
    inv_mod[1] = 1
    for i in range(2,n+1):
        inv_mod[i] = mod - inv_mod[mod%i] * (mod//i ) % mod
    
    return inv_mod

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

x_dif = [x2-x1 for x1,x2 in zip(x,x[1:])]

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

inv = inv_mod(n,MOD) 
    
ans = 0
count = 0
for i,dist in enumerate(x_dif,1):
    count += (fac * inv[i]) %MOD
    count %= MOD
    
    ans += (dist * count)%MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
def cmbmod(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = result*int(numerator[k])%mod
    return result
N=int(input())
X = list(map(int,input().split()))
T=0
mod=10**9+7
pmod=0
A=math.factorial(N-1)%mod
for i in range(1,N):
 pmod+=powmod(i, mod - 2, mod)
 T+=(X[i]-X[i-1])*pmod
 T%=mod
print((A*T)%mod)