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:
# -*- 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 % MOD)
    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 = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
coef = [0] * MAX

fac[0:2] = (1, 1)
finv[0:2] = (1, 1)
inv[1] = 1
coef[0:2] = (1, 1)

for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * int(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 % MOD)
    return

main()

Submission status: Accepted

Solution code:
import sys
 
mod=10**9+7
N=input()
X=map(int, sys.stdin.readline().split())
L=map(lambda x: pow(x,mod-2,mod), range(1,N))
 
L_RUISEKI=[]
 
for i,x in enumerate(L):
    if i==0: L_RUISEKI.append(x)
    else: L_RUISEKI.append(L_RUISEKI[-1]+x)
 
ans=0
for i in range(N-1):
    value=X[i+1]-X[i]
    ans+=value*L_RUISEKI[i]
 
 
fact=[1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
 
print ans*fact[N-1]%mod

Submission status: Accepted

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

mod=10**9+7
N=input()
X=map(int, sys.stdin.readline().split())
L=map(lambda x: pow(x,mod-2,mod), range(1,N))

L_RUISEKI=[]

for i,x in enumerate(L):
    if i==0: L_RUISEKI.append(x)
    else: L_RUISEKI.append(L_RUISEKI[-1]+x)

ans=0
for i in range(N-1):
    value=X[i+1]-X[i]
    ans+=value*L_RUISEKI[i]


fact=[1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)

print ans*fact[N-1]%mod

Submission status: Accepted

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

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

fact, rfact = prepare(N, MOD)

ret = 0
inv = 0
for i in range(N-1):
    diff = X[i+1] - X[i]
    # rfact[i]はiの階乗の逆元なので、fact[i-1]をかけて、iの逆元を求める
    # 普通にpow(i, MOD-2, MOD)と計算結果は一致する
    inv += fact[i] * rfact[i+1]
    ret += diff * inv
    ret %= MOD

print(ret*fact[N-1]%MOD)

Submission status: Accepted

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

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

fact, rfact = prepare(N, MOD)

ret = 0
inv = 0
for i in range(N-1):
    diff = X[i+1] - X[i]
    inv += fact[i] * rfact[i+1]
    ret += diff * inv
    ret %= MOD

print(ret*fact[N-1]%MOD)

Submission status: Accepted

Solution code:
n = int(input())
x = [int(i) for i in input().split()]
mod = 1000000007

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

l = 0
ans = 0
for i in range(n-2):
    l = (l+x[n-2-i]-x[i])%mod
    f = (fact[n-1]*fact[i]*inv[i+2])%mod
    ans = (ans+l*f)%mod
for i in range(n-1):
    l = (x[n-1]-x[n-2-i])%mod
    ans = (ans+((fact[n-1]*fact[i]%mod)*inv[i+1]%mod)*l%mod)%mod
print(ans)

Submission status: Accepted

Solution code:
n =int(input())
x = list(map(int,input().split()))
MOD = 10**9+7
f =[0,1]  
g =[0,1] 
c = 0
ans = 0
for j in range(1,n+1):
    f.append((f[-1]*j)%MOD)
    g.append((g[-1]*(n-j))%MOD)

for i in range(1,n):
    c = (c*i + f[i])%MOD
    ans = (ans+c*(x[i]-x[i-1])*g[n-i])%MOD
print(ans)

Submission status: Accepted

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

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

c = [1 for _ in range(N)]
for i in range(1,N):
  c[i] = c[i-1] + pow(i+1,MOD-2,MOD) # 1/(i+1)を加算
  c[i] %= MOD

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

Submission status: Accepted

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

# ある区間X[3] - X[2]をあるスライムが通過する確率
# 3番目のスライムが通過する確率:1 (必ず通過する。3!=6通り。123, 132, 231, 213, 312, 321)
# 2番目のスライムが通過する確率:1/2 (先に3が選ばれる必要がある。3/6=1/2)
# 1番目のスライムが通過する確率:1/3 (先に3,2が選ばれる必要がある。2/6=1/3)
# ある区間X[i+1] - X[i]についてあるスライムi-jが通過する確率は 1/(j+1)

# 1 = 1
# 2 = 1 + 1/2 = 3/2
# 3 = 1 + 1/2 + 1/3 = 11/6
# 4 = 1 + 1/2 + 1/3 + 1/4 = 25/12
# 5 = 1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60

# 各区間の確率係数を求めてかけた場合
# for i in range(N-1):
#     d = X[i+1]-X[i]
#     p = 1
#     for j in range(1, i+1):
#         p += 1/(j+1)
#     ans += d * p % mod

# あるスライムから最後までの総距離ごとの確率
# ここがよくわからん。前計算を理解できてない
for i in range(N-1):
    d = X[N-1]-X[i]
    ans += d * pow(i+1, mod-2, mod)

# (N-1)!
a = 1
for i in range(1, N):
    a *= i
    a %= mod

ans *= a
ans %= mod
print(int(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


ans=0
x=0

def pow_r(x, n):
    """
    O(log n)
    """
    x %= mod
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%mod
    else:  # standard case ② n is odd
        return (x * (pow_r(x ** 2, (n - 1) // 2)))%mod

for i in range(N-1):
    #(i+1)%(mod-2)を計算してyへ
    y = pow_r(i+1,mod-2)
    #x+= kaijou//(i+1))%(10**9+7)
    x += kaijou*y
    ans += d[i]*x
    ans %= mod

print(ans)

Submission status: Accepted

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

mod = 10**9+7

#互いに素なa,bについて、a*x+b*y=1の一つの解
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=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


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

NN = [1]
for n in range(1, N+1):
    NN.append(NN[-1]*n%mod)

div = 0
ans = 0
for i in range(N-1):
    div = (div + NN[N-1]*mod_inv(i+1) % mod) % mod
    ans = (ans + div*(A[i+1]-A[i])%mod) % mod

print(ans)

Submission status: Accepted

Solution code:
import statistics
import math

MOD = 10**9+7


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

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

    fact = math.factorial(n-1) % MOD
    print(t * fact % MOD)


main()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod 1000000007)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def solve(N: int, x: "List[int]"):
    facts = make_facts(N)
    f = facts[N - 1]
    ret = 0
    cur = 0
    for i in range(N - 1):
            d = x[i + 1] - x[i]
            cur += get_fraction_mod(f, i + 1)
            tmp  = d * cur
            ret += tmp
            ret %= MOD
    print(ret)
    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:
import numpy as np
from math import factorial
MOD = 10**9 + 7

n = int(input())

dist = np.diff(list(map(int, input().split())))
L = np.cumsum(np.array([1 / x for x in range(1, n)]))
n_1 = factorial(n-1) % MOD

# fac = [1] * n
# for i in range(1,n):
# 	fac[i] = fac[i-1] * i % MOD

# print(int(np.sum(L * dist * n_1)) % MOD)
# ans = 0
# for l, d in zip(L, dist):
#     print("l d ", l * d)
#     ans += l * d
#     ans %= MOD

ans = 0
tmp = 0
for i, d in enumerate(dist):
    tmp += pow(i+1, MOD-2, MOD)
    ans += tmp * d
    ans %= MOD

# print(n_1)
print(ans * n_1 % MOD)
# print(int(np.sum(dist * L * n_1) % MOD))

Submission status: Accepted

Solution code:
# 部分点解法

def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

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

    fact = [1]
    for i in range(1, n + 1):
        fact.append(fact[-1] * i % MOD)  # %MODをつけた以外はTLEのコードのまま

    dist_to_r_edge = [x[-1] - x_ for x_ in x[:-1]]

    ret = reduce(
        lambda a, b: (a + b) % MOD,
        (
            d * pow(i, MOD - 2, MOD)
            for i, d in enumerate(dist_to_r_edge, 1)
        )
    )
    print(ret * fact[n - 1] % MOD)


if __name__ == '__main__':
    main()

# ret = 0
# for i, d in enumerate(dist_to_r_edge, 1):
#     ret = (ret + d * pow(i, MOD - 2, MOD)) % MOD
# print(ret * fact[n - 1] % MOD)

Submission status: Accepted

Solution code:
def build_cumsum_invs(ub, mod):
    ret = [0]
    t = 0
    for i in range(1, ub + 1):
        t = (t + pow(i, mod - 2, mod)) % mod
        ret.append(t)
    return ret


def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

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

    coef = build_cumsum_invs(ub=n, mod=MOD)
    # <---><---><---><---><--->
    # x1/1  1/2  1/3  1/4  1/5
    #      x1/1  1/2  1/3  1/4
    #           x1/1  1/2  1/3
    # x点から移動開始したスライムが区間を通過する確率
    # 縦に和をとると、逆数の累積和coefになっている

    prob = reduce(
        lambda a, b: (a + b) % MOD,
        (
            (x[i] - x[i - 1]) * coef[i]
            for i in range(1, n)
        )
    )

    f = reduce(
        lambda a, b: a * b % MOD,
        range(1, n)
    )

    print((prob * f) % MOD)


if __name__ == '__main__':
    main()

# prob = 0
# for i in range(1, n):
#     prob = (prob + (x[i] - x[i - 1]) * coef[i]) % MOD
# ret = (prob * reduce(lambda a, b: a * b % MOD, range(1, n))) % MOD
# print(ret)

Submission status: Accepted

Solution code:
# 部分点

def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

    n = int(input())
    *x, r = map(int, input().split())

    dist_to_r_edge = [r - x_ for x_ in x]

    ret = reduce(
        lambda a, b: (a + b) % MOD,
        (
            d * pow(i, MOD - 2, MOD)
            for i, d in enumerate(dist_to_r_edge, 1)
        )
    )

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

    print(ret * f % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    icumsum = [None] * (size + 1)
    icumsum[1] = 1
    for i in range(1, size):
        icumsum[i+1] = (icumsum[i] + fac[i] * ifac[i+1]) % p
    return fac, ifac, icumsum

fac, ifac, icumsum = make_table(10**5)

n, *x = map(int, sys.stdin.read().split())

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

    res = 0
    for i in range(n-1):
        res += d[i] * icumsum[i+1]
        res %= MOD

    return res * fac[n-1] % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    icumsum = [None] * (size + 1)
    icumsum[1] = 1
    for i in range(1, size):
        icumsum[i+1] = (icumsum[i] + fac[i] * ifac[i+1]) % MOD
    return fac, ifac, icumsum

fac, ifac, icumsum = make_table(10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, *x = map(int, sys.stdin.read().split())

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

    res = 0
    for i in range(n-1):
        res += d[i] * icumsum[i+1]
        res %= MOD

    return res * fac[n-1] % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, *x = map(int, sys.stdin.read().split())

def main():
    d = [x[i+1] - x[i] for i in range(n-1)]
    table = [pow(i, MOD-2, MOD) for i in range(1, n+1)]
    for i in range(n-1):
        table[i+1] += table[i]
        table[i+1] %= MOD

    res = 0
    for i in range(n-1):
        res += d[i] * table[i]
        res %= MOD

    return res * fac[n-1] % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

def main():
    N = ri()
    X = ria()
    p = [mint(0)] * (N - 1)
    p[0] = mint(1)
    for i in range(1,N-1):
        p[i] = p[i-1] + (mint(1) / (i + 1))
    
    tot = mint(0)
    for i in range(N-1):
        tot += (X[i+1] - X[i]) * p[i]
    
    for i in range(1,N):
        tot *= i
    print (tot)

class mint:
    mod = int(1e9 + 7)
    def __init__(self, v = 0):
        if not ((v >= 0) and (v < mint.mod)):
            v %= mint.mod
            if v < 0: v += mint.mod
        self.V = v
    def __add__(self, other):
        v = self.V + (other.V if isinstance(other, mint) else other)
        return mint(v)
    def __sub__(self, other):
        v = self.V - (other.V if isinstance(other, mint) else other)
        return mint(v)
    def __mul__(self, other):
        v = self.V * (other.V if isinstance(other, mint) else other)
        return mint(v)
    def __floordiv__(self, other):
        v = self.V * mint.inv((other.V if isinstance(other, mint) else other))
        return mint(v)
    def __truediv__(self, other):
        v = self.V * mint.inv((other.V if isinstance(other, mint) else other))
        return mint(v)
    
    def __eq__(self, other):
        return self.V == (other.V if isinstance(other, mint) else mint(other).V)
    def __ne__(self, other):
        return self.V != (other.V if isinstance(other, mint) else other)
    def __int__(self): return self.V
    # right operand
    def __radd__(self, other):
        v = (other.V if isinstance(other, mint) else other) + self.V
        return mint(v)
    def __rsub__(self, other):
        v = (other.V if isinstance(other, mint) else other) - self.V
        return mint(v)
    def __rmul__(self, other):
        v = (other.V if isinstance(other, mint) else other) * self.V
        return mint(v)
    def __rfloordiv__(self, other):
        v = (other.V if isinstance(other, mint) else other) * mint.inv(self.V)
        return mint(v)
    def __rtruediv__(self, other):
        v = (other.V if isinstance(other, mint) else other) * mint.inv(self.V)
        return mint(v)

    @staticmethod
    def inv(x):
        a, _, _ = mint.extGCD(x, mint.mod)
        return (a + mint.mod) % mint.mod
    @staticmethod
    def extGCD(x, y):
        r0 = x
        r1 = y
        a0 = 1
        a1 = 0
        b0 = 0
        b1 = 1
        while(r1 > 0):
            q1 = r0 // r1
            r2 = r0 % r1
            a2 = a0 - q1 * a1
            b2 = b0 - q1 * b1
            r0 = r1; r1 = r2
            a0 = a1; a1 = a2
            b0 = b1; b1 = b2
        c = r0
        a = a0
        b = b0       
        return a, b, c
    @staticmethod
    def pow(x, k):
        x = x.V if isinstance(x, mint) else x
        return pow(x, k, mint.mod)

    
    def __str__(self):
        return str(self.V)
    def __repr__(self):
        return str(self.V)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


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

modFacts, invs = prepare(N)

ans = 0
var = modFacts[N - 1]
p = 0
for i in range(N - 1):
    j = i + 1
    d = X[i + 1] - X[i]
    p += modFacts[N - 1] * modFacts[j - 1] * invs[j]
    ans += (d * p) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math

mod = 10**9 + 7

n = int(input())
x = list(map(int,input().split()))
dis = [x[i]-x[i-1] for i in range(1,n)]
f = (math.factorial(n-1))%mod
def modinv(a, mod=mod):
    return pow(a, mod-2, mod)

count = 0
suminv = 0
for i in range(1,n):
    suminv += modinv(i)
    suminv %= mod
    count += dis[i-1]*suminv
    count %= mod
count = (count*f)%mod

print(int(count))

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int, input().split()))
dist = [x[i+1]-x[i] for i in range(n-1)]
mod = 10 ** 9 + 7

fact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
now = fact[n-1]
ans = 0
for k,d in enumerate(dist):
  ans = (ans + now * d) % mod 
  now += (fact[n-1] * pow(k+2,mod-2,mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int, input().split()))
dist = [x[i+1]-x[i] for i in range(n-1)]
mod = 10 ** 9 + 7

fact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
now = fact[n-1]
ans = 0
for k,d in enumerate(dist):
  ans = (ans + now * d) % mod 
  now += (fact[n-1] * pow(k+2,mod-2,mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
N,*X=map(int,open(0).read().split());M,g,r,h=10**9+7,1,0,[1]
while N:N-=1;h+=[h[-1]*N%M]
while h[-~N]:r,g=(r+g*h[-3-N]*(X[-1]-X[N]))%M,g*-~N%M;N+=1
print(r)

Submission status: Accepted

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

mod = 10**9+7


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

    r1 = [1]
    r2 = [1]
    for i in range(N-1):
        r1.append(r1[i] * (i+1) % mod)
        r2.append(r2[i] * (N-1-i) % mod)
    r2.reverse()

    ans = 0
    r = 0
    for i in range(N-1):
        r += r1[i] * r2[i+1]
        ans += (X[i+1] - X[i]) * r
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# B - Fusing Slimes

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

# n! (MOD p)
def factorial_mod(n, p):
    tmp = 1
    for i in range(1, n+1):
        tmp *= i
        tmp %= p
    return tmp

# 逆数の累積和
rv = [1]
for i in range(2, N):
    rv.append(rv[-1] + pow(i, MOD-2, MOD))

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

ans *= factorial_mod(N-1, MOD)
ans %= MOD
print(ans)

Submission status: Accepted

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

f = 1
d = 0
A = 0
 
for i in range(1, n):
  d = (d*i + f) % m
  A = (A*i + (l[i]-l[i-1])*d) % m
  f = f*i % m
 
print(A)

Submission status: Accepted

Solution code:
N,*X=map(int,open(0).read().split());M,g,r,h,i=10**9+7,1,0,[1],N
while i:i-=1;h+=[h[-1]*i%M]
while i<N:r,g=(r+g*h[N-2-i]*(X[-1]-X[i]))%M,g*-~i%M;i+=1
print(r)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = list(map(int, input().split()))
    mod = 10**9 + 7
    X = []
    for i in range(n - 1):
        X.append(x[i + 1] - x[i])
    l, left = 1, [1]
    for i in range(1, n - 1):
        l *= i
        l %= mod
        left.append(l)
    r, right = 1, [1]
    for i in range(n - 1, 1, -1):
        r *= i
        r %= mod
        right.append(r)
    right.reverse()
    f, flst = 0, []

    for i, j in zip(left, right):
        f += i * j % mod
        f %= mod
        flst.append(f)
    s = 0
    for i, j in zip(X, flst):
        s += i * j % mod
    print(s % mod)
main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n = int(input())
l = list(map(int, input().split()))
 
d, ans = 0, 0
 
for i in range(1, n):
  f = 1 if i == 1 else f * (i-1) % mod
  d = (d * i + f) % mod
  ans = (ans * i + (l[i] - l[i-1]) * d) % mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = int(1e+9 + 7)


class Comb(object):
    def __init__(self, n, MOD=1e9+7):
        self.n = n
        self.MOD = MOD

        fac = [0] * self.n
        finv = [0] * self.n
        inv = [0] * self.n

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1

        for i in range(2, n):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[(MOD % i)] * (MOD // i) % MOD
            finv[i] = finv[i-1] * inv[i] % MOD
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calv(self, k):
        if self.n < k:
            return 0

        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.MOD) % self.MOD


N, *X = map(int, read().split())
X = np.array(X)
X_diff = np.diff(X)

comb = Comb(N+5, MOD)

acc = 0
ans = 0
for i in range(1, N):
    acc += comb.fac[N-1] * comb.inv[i]
    acc %= MOD

    ans += acc * (X_diff[i-1])
    ans %= MOD


print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read

n, *X = map(int, read().split())
mod = 10**9 + 7
last = X[-1]
X = [last - i for i in X[:-1]]
a, left = 1, [1]
for i in range(1, n - 1):
    a *= i  # メモリ
    a %= mod  # メモリ
    left.append(a)
b, right = 1, [1]
for i in range(n - 1, 1, -1):
    b *= i  # メモリ
    b %= mod  # メモリ
    right.append(b)
right.reverse()
flst = [(i * j % mod) % mod for i, j in zip(left, right)]
s = sum(i * j % mod for i, j in zip(X, flst))
print(s % mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
x = list(map(int, input().split()))
g = [0]
for i in range(n-1):
	g.append(x[i+1]-x[i])
ans = 0
coef = 0
for i in range(1, n):
	coef += pow(i, MOD-2, MOD)
	ans += coef * g[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())
lx = list(map(int, input().split()))

d = 0
ans = 0

for i in range(1, n):
  f = 1 if i == 1 else f * (i-1) % mod
  d = (d * i + f) % mod
  ans = (ans * i + (lx[i] - lx[i-1]) * d) % mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
X = list(map(int, input().split()))
mod = 10**9 + 7
last=X[-1]
X=[last-i for i in X[:-1]]
l, left = 1, [1]
for i in range(1, n - 1):
    l *= i
    l %= mod
    left.append(l)
r, right = 1, [1]
for i in range(n - 1, 1, -1):
    r *= i
    r %= mod
    right.append(r)
right.reverse()
flst=[(i*j%mod)%mod for i,j in zip(left,right)]
s = sum(i*j%mod for i,j in zip(X,flst))
print(s%mod)

Submission status: Accepted

Solution code:
import math

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

def c(n):
    if n == 1:
        return 1
    return c(n - 1) + 1 / n

mod = 10 ** 9 + 7
sum = 0
c = 0
for i in range(n - 1):
    c += pow(i + 1, mod - 2, mod)
    c %= mod
    sum += (x[i + 1] - x[i]) * c
    sum %= mod
ans = (sum * math.factorial(n - 1)) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
X = []
for i in range(n - 1):
    X.append(x[i + 1] - x[i])
l, left = 1, [1]
for i in range(1, n - 1):
    l *= i
    l %= mod
    left.append(l)
r, right = 1, [1]
for i in range(n - 1, 1, -1):
    r *= i
    r %= mod
    right.append(r)
right.reverse()
f, flst = 0, []

for i, j in zip(left, right):
    f += i * j % mod
    f %= mod
    flst.append(f)
s = 0
for i, j in zip(X, flst):
    s += i * j % mod
print(s % mod)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426910


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

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

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

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

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

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

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

    print(ans)

solve()

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 = [0] + LIST()
B = [A[i+1] - A[i] for i in range(N)]

mt = ModTools(N, MOD)
add = mt.fact[N-1]
# スライムが区間iを通る合計回数をそれぞれ求める
cnt = [0] * N
for i in range(1, N):
    cnt[i] = 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())
x = list(map(int, input().split()))

mod = 10 ** 9 + 7

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

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

print(ans)