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 ModWorld:
    def __init__(self, mod):
        self.mod = mod

    def prepare_factorial(self, N):
        self.f = [1] # f[n] := n!
        p = 1
        for i in range(1,N+1):
            p = (p*i) % self.mod
            self.f.append(p)

    def modpow(self, x, k):
        x %= self.mod
        k %= self.mod-1 # a^(p-1) = 1
        retval = 1
        while k:
            if k&1: retval = retval * x % self.mod
            k>>=1
            x = x*x % self.mod
        return retval % self.mod

    def modcomb(self, n, k):
        return self.f[n] * self.modpow(self.f[n-k], -1) * self.modpow(self.f[k], -1) % self.mod

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

mw = ModWorld(mod=10**9+7)
mw.prepare_factorial(N=10**5)

ans = k = 0
for i, d in enumerate(D):
    k = (k + mw.f[N-1]*mw.modpow(i+1, -1)) % mw.mod
    ans = (ans + d*k) % mw.mod

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    #########################################
    fact = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%MOD
        fact.append(new_fact)
    #########################################
    count = 2
    for i in range(1,N-1): 
        tmp = goal - X[i]
        ########################################################
        ans = ((ans * count) + ((fact[i] * tmp))) % MOD
        ########################################################
        count += 1  
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    fact = [1]
    fact_inv = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%MOD
        fact.append(new_fact)
    count = 1
    for i in range(1,N-1):
        count += 1
        tmp = goal - X[i]
        ans = ((ans * count) + ((fact[i] * tmp))) % MOD  
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#1/i!でなく1/iだった
n = int(input())
x = list(map(int, input().split( )))
mod = 10**9+7
#rev_fact = []
rev = []
res = 1
for i in range(1,n):
     rev_i = pow(i,mod-2,mod)
     #res *= rev_i
     #res %= mod
     #rev_fact.append(res)
     rev.append(rev_i)

n_fact = 1

for i in range(1,n):
    n_fact*=i
    n_fact%=mod
#print(n_fact)
ans = 0
tmp = 0
for i in range(n-1):
    tmp += rev[i]
    ans += (x[i+1]-x[i])*tmp
    ans %= mod
ans*=n_fact
ans%=mod
print(ans)

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

class ModArray(np.ndarray):
    def __new__(cls, input_array, info=None):
        obj = np.asarray(input_array, dtype=np.int64).view(cls)
        return obj
    
    @classmethod
    def zeros(cls, *args):
        obj = np.zeros(*args, dtype=np.int64)
        return obj.view(cls)
    
    @classmethod
    def ones(cls, *args):
        obj = np.ones(*args, dtype=np.int64)
        return obj.view(cls)
    
    @classmethod
    def arange(cls, *args):
        obj = np.arange(*args, dtype=np.int64) % MOD
        return obj.view(cls)
    
    @classmethod
    def powers(cls, a, N):
        B = N.bit_length()
        x = cls.ones(1<<B)
        for n in range(B):
            x[1<<n:1<<(n+1)] = x[:1<<n] * a
            a *= a; a %= MOD
        return x[:N]
    
    @classmethod
    def _set_constant_array(cls, N):
        x = cls.arange(N); x[0] = 1
        fact = x.cumprod()
        x = cls.arange(N,0,-1); x[0] = pow(int(fact[-1]), MOD-2, MOD)
        fact_inv = x.cumprod()[::-1]
        inv = cls.zeros(N)
        inv[1:N] = fact_inv[1:N] * fact[0:N-1]
        fact.flags.writeable = False
        fact_inv.flags.writeable = False
        inv.flags.writeable = False
        cls._fact = fact; cls._fact_inv = fact_inv; cls._inverse = inv
        
    @classmethod
    def fact(cls, N):
        if (getattr(cls, '_fact', None) is None) or len(cls._fact) < N:
            cls._set_constant_array(max(N, 10 ** 6))
        return cls._fact[:N]

    @classmethod
    def fact_inv(cls, N):
        if (getattr(cls, '_fact', None) is None) or len(cls._fact) < N:
            cls._set_constant_array(max(N, 10 ** 6))
        return cls._fact_inv[:N]

    @classmethod
    def inverse(cls, N):
        if (getattr(cls, '_fact', None) is None) or len(cls._fact) < N:
            cls._set_constant_array(max(N, 10 ** 6))
        return cls._inverse[:N]
    
    @classmethod
    def _convolve_small(cls, f, g):
        Lf = len(f); Lg = len(g); L = Lf + Lg - 1
        if min(Lf, Lg) < 100 or Lf + Lg < 300:
            return (np.convolve(f,g) % MOD).view(cls)
        else:
            fft = np.fft.rfft; ifft = np.fft.irfft; n = 1 << L.bit_length()
            return (np.rint(ifft(fft(f, n) * fft(g, n))[:L]).astype(np.int64) % MOD).view(cls)
    
    @classmethod
    def convolve(cls, f, g):
        if f.max() < (1<<15) and g.max() < (1<<15):
            return cls._convolve_small(f, g)
        Lf = len(f); Lg = len(g); L = Lf + Lg - 1
        fl = f & (1 << 15) - 1; fh = f >> 15
        gl = g & (1 << 15) - 1; gh = g >> 15
        x = cls._convolve_small(fl, gl)
        z = cls._convolve_small(fh, gh)
        y = cls._convolve_small(fl+fh, gl+gh) - x - z
        return x + (y<<15) + (z<<30)
    
    def resize(self, N):
        L = len(self)
        if L >= N:
            return self[:N]
        A = np.resize(self, N).view(self.__class__)
        A[L:] = 0
        return A
    
    def diff(self):
        return np.diff(self) % MOD
               
    def cumprod(self):
        L = len(self); Lsq = int(L**.5+1)
        A = self.resize(Lsq**2).reshape(Lsq, Lsq)
        for n in range(1,Lsq):
            A[:,n] *= A[:,n-1]
        for n in range(1,Lsq):
            A[n] *= A[n-1,-1]
        return A.ravel()[:L]

    def __array_wrap__(self, out_arr, context=None):
        if context and context[0] == np.mod:
             return out_arr
        if out_arr.dtype == np.int64:
            np.mod(out_arr, MOD, out=out_arr)
            return out_arr
        else:
            return np.asarray(out_arr)

N = int(readline())
X = ModArray(read().split())

U = 10 ** 5 + 100
inv = ModArray.inverse(U)
fact = ModArray.fact(U)

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

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

print(answer)

Submission status: Accepted

Solution code:
#----------------------------------------------------------
P = 10**9 + 7
N = 100001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or a<0 or b<0:
        return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P
#----------------------------------------------------------

n=int(input())
x=list(map(int,input().split()))
s = [0] * n
for i in range(n):
    s[i] = x[i] + (s[i-1] if i>0 else 0)
ans=0

for i in range(n-1):
    t = (x[n-1]-x[n-2-i])%P
    t = (t * (fac[n-1]*inv[i+1])%P)%P
    ans=(ans+t)%P
for i in range(1, n-1):
    t = (s[n-2] - s[i-1] - s[n-2-i])%P
    p = (((fac[n-1] * inv[i])%P) * inv[i+1])%P
    ans = (ans + (t*p)%P)%P

print(ans%P)

Submission status: Accepted

Solution code:
from math import ceil
N = int(input())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7

# 間の距離を計算
distances = [0] + [X[i + 1] - X[i] for i in range(N - 1)]

# (N - 1)!を計算
factorial_n_1 = 1
for i in range(1, N):
    factorial_n_1 *= i
    factorial_n_1 %= MOD


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

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

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


N = int(sys.stdin.buffer.readline())
X = list(map(int, sys.stdin.buffer.readline().split()))

invs = mod_invs(max=N + 10, mod=MOD)
invs[0] = 0
# invs_cum[i]: 1/1 + 1/2 + 1/3 + ... + 1/i
invs_cum = np.cumsum(invs).tolist()

D = np.diff(X)
ans = 0
for i in range(len(D)):
    # スライムごとに各道を使う期待値を考えると、
    # 道 i を使う期待値は 1/1 + 1/2 + ... + 1/i だと分かる
    ans += D[i] * invs_cum[i + 1]
    ans %= MOD
# ans *= (N-1)!
for i in range(1, N):
    ans *= i
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


def test2(X):
    ret = 0
    for xs in itertools.permutations(X[:-1]):
        print(xs)
        a = 0
        ss = list(X)
        for x in xs:
            ret += ss[ss.index(x) + 1] - x
            a += ss[ss.index(x) + 1] - x
            ss.remove(x)
            print(ss)
        print(a)
        print()
    print(ret % MOD)
    print()
    print()


N = int(sys.stdin.buffer.readline())
X = list(map(int, sys.stdin.buffer.readline().split()))

inv2 = pow(2, MOD - 2, MOD)


def div2(n):
    return n % MOD * inv2 % MOD


def diff(A):
    ret = []
    for a, b in zip(A, A[1:]):
        ret.append(b - a)
    return ret


factorials = get_factorials(N + 10, MOD)
# test2(X)
# test(np.diff(X))

st = [0]
# 何回使うか
# わからんぽん
# https://oeis.org/A000254
for i in range(N + 1):
    st.append((i + 1) * st[-1] % MOD + factorials[i])

comb = Combination(max=N + 10, mod=MOD)
ans = 0
for i, d in enumerate(diff(X)):
    ans += d * st[i + 1] % MOD * comb.ncr(N, i + 1) % MOD * factorials[N - i - 1] % MOD
    ans %= MOD
ans *= pow(N, MOD - 2, MOD)
ans %= MOD
print(ans)

# for i in range(8):
#     N = i
#     counts = [0] * (N + 1)
#     for order in itertools.permutations(range(N)):
#         used = np.zeros(N)
#         a = 0
#         for i in order:
#             if used[:i].sum() == 0:
#                 a += 1
#                 used[i] = 1
#         counts[a] += 1
#     print(N)
#     print(counts)
#     print(counts * np.arange(N + 1))
#     print((counts * np.arange(N + 1)).sum())
#     print()

Submission status: Accepted

Solution code:
mod=10**9+7
# mod inverse(逆元)
# 今回はfermatの小定理で求める
def mod_inv(x):
  return pow(x,mod-2,mod)

n=int(input())
A=list(map(int,input().split()))
# (N-1)!を求める
fac=1
for i in range(1,n):
  fac = fac*i%mod
# 各区間の個数テーブルを先に求める
cnt=[0]*n
for i in range(1,n):
  cnt[i] = fac * mod_inv(i) % mod
  cnt[i] = (cnt[i]+cnt[i-1]) % mod
# 計算
ans=0
for i in range(n-1):
  ans += (A[i+1]-A[i]) * cnt[i+1]
  ans %= mod

print(ans)

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]]

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

ans = 0
MOD = 10**9 + 7

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,MOD)
    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:
# -*- coding: utf-8 -*-

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 100005
MOD = 1000000007
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

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

ans = 0
prepro = [1]
for i in range(2, N+1):
    prepro.append((prepro[-1]+inverse[i]) % MOD)

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

ans *= factrial[N-1]  # 総和に(N-1)!をかける

print(ans % MOD)

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 100005
MOD = 1000000007
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

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

ans = 0
prepro = [1]
for i in range(2, N+1):
    prepro.append((prepro[-1]+inverse[i]) % MOD)

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

ans *= factrial[N-1]  # 期待値の総和に(N-1)!をかける

print(ans % MOD)

Submission status: Accepted

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


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)

Submission status: Accepted

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

Submission status: Accepted

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

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

d = [0]*(N-1)

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


kaijou = 1
for i in range(1,N):
    i %= mod
    kaijou *= i
    kaijou %= mod #これをしないとkaijouが発散


ans=0
x=0

def pow_a(a,n): #(modを取るように改良)
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= a
            K %= mod
        a *= a
        a %= mod
        n //= 2

    return (K*a)%mod

for i in range(N-1):
    y = pow_a(i+1,mod-2) #i+1の逆元
    x += kaijou*y
    ans += d[i]*x
    ans %= mod

print(ans)

Submission status: Accepted

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

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

d = [0]*(N-1)

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


kaijou = 1
for i in range(1,N):
    kaijou *= i
    kaijou %= mod #これをしないとkaijouが発散


ans=0
x=0

def pow_a(a,n): #(modを取るように改良)
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= a
            K %= mod
        a *= a
        a %= mod
        n //= 2

    return K*a

for i in range(N-1):
    y = pow_a(i+1,mod-2) #i+1の逆元
    x += kaijou*y
    ans += d[i]*x
    ans %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int,input().split()))
ans=math.factorial(n-1)%(10**9+7)

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

c=0
for i in range(1,n):
    c+=(a[-1]-a[i-1])*modinv(i, mod=10**9+7)
print(ans*c%(10**9+7))

Submission status: Accepted

Solution code:

n=int(input())
a=[int(k) for k in input().strip().split(" ")]
ai=a[::-1]
res=0

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

sa=[0]
for k in a:
    sa+=[(sa[-1]+k)%mod]

def ssum(l,r):
    return (sa[r+1]-sa[l])%mod

b=[[0 for i in range(2)] for j in range(n-1)]
b[0][0]=fact[n-1]
b[0][1]=(b[0][0]*pow(2,mod-2,mod))%mod
res+=(b[0][0]*(a[-1]-a[-2]))%mod
if n>2:
    res+=(b[0][1]*(ssum(1,n-2)-ssum(0,n-3)))%mod
for j in range(2,n):
    b[j-1][0]=(b[j-2][0]*(j-1) * pow(j,mod-2,mod))%mod
    res+=(b[j-1][0]*(a[-1]-a[-j-1]))%mod
    if j<n-1:
        b[j-1][1]=(b[j-2][1]*(j-1) * pow(j+1,mod-2,mod))%mod
        res+=(b[j-1][1]*(ssum(j,n-2)-ssum(0,n-j-2)))%mod

print(res%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
#import numpy as np
n = int(input())
X = list(map(int, input().split()))
C=[1 for a in range(n-1)]
mod = 10 ** 9 + 7
fac = math.factorial(n - 1) % mod

for i in range(1,n - 1):
    len=i+1#左にあるスライムの個数
    C[i]=C[i-1]+ pow(len, mod - 2,mod)
    C[i]%=mod

ans = 0
for i in range(n-1):
    ans+=C[i]*(X[i+1]-X[i])
    ans%=mod
ans*=fac
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import math
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)]
N_1=N-1
upp=math.factorial(N_1)%MOD
  
b=[0]*(N_1)
b[0]=upp
tmp=upp
out=b[0]*y[0]%MOD
for i in range(1, N_1):
  a=tmp*pow(i+1, MOD-2, MOD)%MOD
  b[i]=(b[i-1]+a)%MOD
  out+=b[i]*y[i]%MOD
  out%=MOD
print(out)

Submission status: Accepted

Solution code:
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
for i in range(2, N):
  upp*=i
  upp%=MOD
  
N_1=N-1
b=[0]*(N_1)
b[0]=upp
tmp=upp
out=b[0]*y[0]%MOD
for i in range(1, N_1):
  a=tmp*pow(i+1, MOD-2, MOD)%MOD
  b[i]=(b[i-1]+a)%MOD
  out+=b[i]*y[i]%MOD
  out%=MOD
print(out)

Submission status: Accepted

Solution code:
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
  
N_1=N-1
b=[0]*(N_1)
b[0]=upp[N_1]
tmp=upp[N_1]
for i in range(1, N_1):
  a=tmp*pow(i+1, MOD-2, MOD)%MOD
  b[i]=(b[i-1]+a)%MOD


print(sum([b[i]*y[i]%MOD for i in range(N_1)])%MOD)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 1000000007  # type: int
import math
from itertools import accumulate

def mod_factorial(n):
    value = 1
    for i in range(n,0,-1):
        value*=i
        value%=MOD

    return value

def solve(N: int, x: "List[int]"):
    dif_x = []
    for i in range(1,N):
        dif_x.append(x[i]-x[i-1])

    # factmod[i] = (N-1)!/iをMODで割ったあまり
    factmod = [0]*(N)
    factmod[1] = mod_factorial(N-1)
    
    for i in range(2,N):
        factmod[i] = factmod[1]*pow(i,MOD-2,MOD)
    
    for i in range(2,N):
        factmod[i] += factmod[i-1]
        factmod[i]%=MOD
        
    answer = 0

    for i in range(N-1):
        answer += factmod[i+1]*dif_x[i]
        answer %= MOD
    
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int
import math
from itertools import accumulate

def mod_factorial(n):
    value = 1
    for i in range(n,0,-1):
        value*=i
        value%=MOD

    return value

def solve(N: int, x: "List[int]"):
    dif_x = []

    # factmod[i] = (N-1)!/iをMODで割ったあまり
    factmod = [0]*(N)
    factmod[1] = mod_factorial(N-1)
    for i in range(1,N):
        dif_x.append(x[i]-x[i-1])
    
    for i in range(2,N):
        factmod[i] = factmod[1]*pow(i,MOD-2,MOD)
    
    accum_fact_mod = list(accumulate(factmod))
        
    answer = 0

    for i in range(N-1):
        answer += accum_fact_mod[i+1]*dif_x[i]
        answer %= MOD
    
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 510000
MOD = 1000000007
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

N = int(input())
X = list(map(int, input().split()))
# expected_value = [1]
# for i in range(2, N):
#     expected_value.append(expected_value[-1]+(1/i))
ans = 0
f = factrial[N-1]
c = 0
for i in range(1, N):
    c += f * inverse[i]
    c %= MOD
    ans += c * (X[i] - X[i-1])
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
import math

n = int(input())
x = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7
f = 1
for i in range(1,n):
  f *= i
  f %= mod

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

ans*=f
ans%=mod


print(ans)

Submission status: Accepted

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

import sys
from math import factorial

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

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

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

add = factorial(N-1) % MOD
# スライムが区間iを通る合計回数をそれぞれ求める
cnt = [0] * N
for i in range(1, N):
    cnt[i] = cnt[i-1] + add
    cnt[i] %= MOD
    add *= fermat(i ,i+1, MOD)
    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())
x=[int(i) for i in input().split()]
d=[x[i+1]-x[i] for i in range(N-1)]
ans=0
tmp=0
N1fact=1
mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
for i in range(1,N):
    N1fact=(i*N1fact)%mod
for k in range(1,N):
    tmp+=inv(k)
    tmp%=mod
    a1=tmp
    a2=(d[k-1]*N1fact)%mod
    #print(a1,a2)
    ans+=(a1*a2)%mod
    ans%=mod
print(ans)
#print(N1fact)
#print((ans*N1fact)%mod)

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int,input().split()))
S = []
dp = [1]
mod = 10**9+7
for i in range(N):
    t = i+1
    dp.append(dp[i]*t%mod)
def power(a,b):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power(a,b//2)
        return d*d%mod
    elif b % 2 == 1:
        return a*power(a,b-1)%mod
W = []
for i in range(1,N):
    y = dp[N-1]*power(i,mod-2)%mod
    W.append(y)
ans = 0
for i in range(N-1):
    x = X[i]
    S.append(X[N-1]-x)
ans = 0
for i in range(N-1):
    x = S[i]
    t = i + 1
    ans += W[i]*x%mod
print(ans%mod)

Submission status: Accepted

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

def euclid(a:int,b:int)->(int,int):
    #return x,y s.t ax + by = gcd(a,b)
    #a > b >= 0
    if b == 0:
        return 1,0
    x,y = euclid(b,a%b)
    return y,x - y*(a // b)

def inverse(a:int,mod:int)->int:
    #gcd(p,b) == 1
    if mod > a:
        n,x = euclid(mod,a)
    else:
        x,n = euclid(a,mod)
    return x

def devide_mod(a:int,b:int,mod:int)->int:
    #a // b
    x = inverse(b,mod)
    return  (a*x)%mod


def main():
    ans = 0
    fraq = [1]*(N)
    S = [0]*(N+1)
    for i in range(1,N):
        fraq[i] = (fraq[ i - 1 ]*i)%mod
    
    for i in range(1,N + 1):
        S[ i ] = (S[ i - 1 ] + devide_mod(fraq[ N - 1 ], i ,mod))%mod

    for i in range(N - 1):
        ans = (ans + (X[ i + 1 ] - X[ i ])*S[ i + 1 ])%mod
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# dwacon6th-prelims/dwacon6th_prelims_b
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())

MAX = 10**5 + 100
MOD = 10**9 + 7

fac = [1, 1] + [0] * MAX
finv = [1, 1] + [0] * MAX
inv = [1, 1] + [0] * MAX
coef = [1, 1] + [0] * MAX

for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
    coef[i] = (coef[i - 1] * i + fac[i - 1]) % MOD

def main():
    N = i2n()
    n = N - 1
    x = i2nn()
    total = 0
    for i in range(1, N):
        d = x[i] - x[i - 1]
        total = (total + coef[i] * fac[n] % MOD * finv[i] % MOD * d % MOD) % MOD
    print(total)
    return

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# dwacon6th-prelims/dwacon6th_prelims_b
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

MAX = 10**5 + 100
MOD = 10**9 + 7

fac = [1, 1] + [0] * MAX
finv = [1, 1] + [0] * MAX
inv = [1, 1] + [0] * MAX
coef = [1, 1] + [0] * MAX

for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
    coef[i] = coef[i - 1] * i % MOD + fac[i - 1] % MOD

def main():
    N = i2n()
    n = N - 1
    x = i2nn()
    total = 0
    for i in range(1, N):
        d = x[i] - x[i - 1]
        total = (total + (coef[i] * fac[n] % MOD * finv[i] % MOD * d % MOD)) % MOD
    print(total)
    return

main()