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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(N, X):
    M = Mod(10**9+7)
    ne = [1]
    for i in range(1, N+1):
        ne.append(M.mul(i, ne[i-1]))

    ans = 0
    for i in range(N-1):
        rem = ne[N-1]
        for j in range(i+1, N-1):
            d = X[j] - X[i]
            c = j - i + 1
            n = M.mul(M.div(ne[N-1], ne[c]), ne[j-i-1])
            rem = M.sub(rem, n)
            ans = M.add(ans, M.mul(d, n))
        ans = M.add(ans, M.mul(X[N-1] - X[i], rem))

    return ans

def slv2(N, X):
    ans = 0
    s = Counter()
    for p in permutations(range(N-1)):
        x = X[:]
        for i in p:
            for j in range(i+1, N):
                if x[j]:
                    break

            ans += x[j] - x[i]
            s[(j, i)] += 1
            x[i] = None
    for i in range(N-1):
        for j in range(i+1, N):
            print(i, j, s[(j,i)])
    return ans

def main():
    N = read_int()
    X = read_int_n()
    print(slv(N, X))
    # print(slv2(N, X))

    # N = 10**5
    # X = list(range(1, N+1))
    # print(slv(N, X))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int,input().split()))
MOD = 10 ** 9 + 7
goal = X[-1]
ans = goal - X[0]
x = 1
for i in range(1,N-1):
    tmp = goal - X[i]
    ans = ((ans * (i+1) % MOD) + ((x*tmp) % MOD)) % MOD
    x *= i+1 % MOD
    #print(tmp,ans,x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = list(map(int, input().split()))
ans = 0
p = math.factorial(n-1)
for i in range(n-1):
  k = p//(i+1) % 1000000007
  ans += k * (x[n-1]-x[i])
  ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

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

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

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


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

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

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
x_dis = [x[i+1] - x[i] for i in range(N-1)]
ans = 0
m = N-1
fac = factorial(m)
tmp = fac
for i in range(m):
    ans += x_dis[i] * tmp
    ans %= mod
    tmp += fac//(i+2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

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

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

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


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

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

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import copy

N=input()
p=input()
dist_total=0
plist_str=p.split(" ")
plist=[int(n) for n in plist_str]

lis = [x for x in range(int(N)-1)]
permutations_lis = itertools.permutations(lis)

for one_case in permutations_lis: 
  plist_=copy.copy(plist)
  for num in one_case:
    dist_total+=plist_[num+1]-plist_[num]
    dist_total%=1000000007
    plist_[num]=plist_[num+1]

print(dist_total)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

# #
n = inn()
x = inl()

modinva = [1]*n
fact = 1
for i in range(2,n):
    modinva[i] = modinv(i,R)
    fact = (fact*i)%R
ddprint(modinva)
ddprint(fact)

sm = 0
for i in range(n-1):
    e = (x[n-1]-x[i])*modinva[n-1-i]
    for j in range(i+1,n-1):
        e += (x[j]-x[i])*modinva[j-i]*modinva[j-i+1]
    sm = (sm+e)%R
print((fact*sm)%R)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int,input().split()))
MOD = 10 ** 9 + 7
goal = X[-1]
ans = goal - X[0]
x = 1
for i in range(1,N-1):
    tmp = goal - X[i]
    ans = (ans * (i+1) + (x*tmp)) % MOD
    x *= i+1
    #print(tmp,ans,x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import permutations
n = int(input())
x = list(map(int, input().split()))

#print(math.factorial(n-1))
#print(10**9 + 7)

# 初期化
sum_d = 0
# indexの順列を生成
seq = (i for i in range(n-1))
juns = list(permutations(seq))
#print(jun)
#print(num_l)

# 移動距離の総和の計算
for jun in juns:
  num_l = set(i for i in range(n))
  #print("junretsu={}".format(jun))
  d = 0
  for k in jun:
    #print("k={}".format(k))
    tmp = 1
    while(not(k+tmp in num_l)):
      #print("{}+{} in {}??".format(k, tmp, num_l))
      #print(k+tmp in num_l)
      tmp += 1
      # 直近のkの右隣を探す 
    d += x[k+tmp] - x[k]
    #print("d={}".format(d))
    num_l.remove(k)
    #print("num_l={}".format(num_l))
    #print("--")
  sum_d += d
  #print("----")
print(sum_d % (10**9 + 7))
#print(n)
#print(x)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

x_max = x.pop(-1)
x_left = x
length = len(x_left)

x_left_list = list(itertools.permutations(x_left, length))
x_left_list = [list(v) for v in x_left_list]

# numpy 配列に。
x_left_array = np.array(x_left_list).reshape(-1, length)
x_max_array = np.array([x_max for i in range(length)]).reshape(-1, 1)
x_all = np.hstack((x_max_array, x_left_array))

x_diff = np.array(np.abs(x_all[:, :-1] - x_all[:, 1:])).reshape(-1)

X = np.sum(x_diff)

print(X)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
import math

N = int(input())

# 空白区切りの数値をリスト化
xn = list(map(int, input().split()))

mod_value = 10**9 + 7


def distance_average(xn):
    return xn[-1] - xn[0]


total_distance = 0

q = queue.Queue()
q.put(xn)

while not q.empty():
    line = q.get()
    total_distance += distance_average(line)

    if len(line) == 1:
        break

    original_line = copy.deepcopy(line)
    editing_line = copy.deepcopy(line)
    for remove_index in range(0, len(line) - 1):
        editing_line.pop(remove_index)
        q.put(editing_line)
        editing_line = copy.deepcopy(original_line)


exp = (total_distance / math.factorial(N-1)) * math.factorial(N-1)

sho, amari = divmod(exp, mod_value)

print(int(amari))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
x = list(map(int, input().split()))
r = 10 ** 9 + 7
p = math.factorial(n - 1)
ans = 0
f = x[n - 1]
for i in range(n-1):
    ans += (f - x[i]) * p
    ans %= r
    p = p * (i + 1) // (i + 2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7
    from math import factorial
    N = II()
    X = LMIIS()
    # f = factorial(N-1)
    # def calc(k,slimes):
    #     # print(slimes)
    #     if k == N-1:
    #         return 0
    #     r = 0
    #     # for i in range(N-k-1):
    #     #     slimes2 = slimes[:]
    #     #     r = (slimes2[i+1]-slimes2[i]) / float(N-k-1)
    #     #     slimes2.pop(i)
    #     #     r += calc(k+1,slimes2) % MOD
    #     i = N-k-2
    #     slimes2 = slimes[:]
    #     print(i,slimes2)
    #     r = (slimes2[i+1]-slimes2[i]) * f / (N-k-1) % MOD
    #     slimes2.pop(i)
    #     r += calc(k+1,slimes2) 
    #     return r % MOD
    f = factorial(N-1)
    def calc(k,slimes):
        if k == N-1:
            return 0
        r = 0


        for k in range(N-1):

            r += (slimes[-1]-slimes[-2-k]) * f // (N-k-1)
            r %= MOD

        return r
    
    print(calc(0,X))




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

d = [0]*(N-1)
for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= 10**9+7

kaijou = 1
for i in range(1,N):
    kaijou *= i%(10**9+7)

ans=0
x=0
for i in range(N-1):
    x+= (kaijou//(i+1))%(10**9+7)
    ans+= d[i]*x

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

fac = [1 for i in range(N)]
inv = [0 for i in range(N)]
for i in range(1, N):
    fac[i] = fac[i-1] * i % sosu
    inv[i] = pow(i, sosu-2, sosu)
#Sprint(fac)
ans = 0
for i in range(N):
    for j in range(i+1, N):
        kyori = X[j] - X[i]
        #print(kyori)
        if j == N-1:
            kaisu = fac[N-1] * inv[j-i] % sosu
            #(N-1)! / (j-i)#= (j-i-1)! * ((j-i-1)+ 1 + 1) * .. * (N-1)
        else:
            kaisu = (fac[N-1] * inv[j-i] % sosu) * inv[j-i+1] % sosu
            #(N-1)! / (j-i)(j-i+1) #(j-i-1)! * ((j-i-1) +2+1) * ... * (N-1)
        #print(kaisu)
        ans += kyori * kaisu % sosu
        ans = ans % sosu
print(ans)



'''
ma = X[N-1] - X[0]
S = [0 for i in range(N-1)]
for i in range(N-1):
    S[i] = X[i+1] - X[i]
kaijo = [1 for i in range(N)]
for i in range(1, N):
    kaijo[i] = kaijo[i-1] * i % sosu

print(S)
'''

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
def fact(a):
    if a == 1:
        return 1
    else: 
        b = 1
        for i in range(1,a+1):
            b *= i
    return b
def xx(a):
    if a == 1:
        return [1] 
    else:
        b = [1]
        for i in range(2, a+1):
            for j in range(len(b)):
                b[j] *= i
            b.append(b[len(b)-1] + fact(i-1))
        return b
y = xx(n-1)
ans = 0
for i in range(n-1):
    ans += y[i] * (x[i+1]-x[i])
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7
    from math import factorial
    N = II()
    X = LMIIS()
    # f = factorial(N-1)
    # def calc(k,slimes):
    #     # print(slimes)
    #     if k == N-1:
    #         return 0
    #     r = 0
    #     # for i in range(N-k-1):
    #     #     slimes2 = slimes[:]
    #     #     r = (slimes2[i+1]-slimes2[i]) / float(N-k-1)
    #     #     slimes2.pop(i)
    #     #     r += calc(k+1,slimes2) % MOD
    #     i = N-k-2
    #     slimes2 = slimes[:]
    #     print(i,slimes2)
    #     r = (slimes2[i+1]-slimes2[i]) * f / (N-k-1) % MOD
    #     slimes2.pop(i)
    #     r += calc(k+1,slimes2) 
    #     return r % MOD
    f = factorial(N-1)
    def calc(k,slimes):
        if k == N-1:
            return 0
        r = 0


        for k in range(N-1):

            r += (slimes[-1]-slimes[-2-k]) * f // (N-k-1) % MOD

        return r % MOD
    
    print(int(calc(0,X)))




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(n-1):
    ans += (f - x[i]) * p
    ans %= r
    p = p * (i + 1) // (i + 2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
d = []
for x1, x2 in zip(x, x[1:]):
    d.append(x2 - x1)
mod = 10 ** 9 + 7
base = 1
for i in range(1, n):
    base *= i
ans = 0
b = base
for i, di in enumerate(d):
    ans += (base * di)  % mod
    ans %= mod
    base += b // (i + 2)
    base % mod
print(ans)

Submission status: Time Limit Exceeded

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

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

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

ans = sum(d) * s % MOD

for i in range(m):
    p = 1
    for j in range(i+1, n-1):
        c = j - i
        p *= c * inv[c+1]
        p %= MOD
        ans += d[j] * p * s
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def per(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r=n-r
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+5
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 )


n=int(input())
A=[1]
for i in range(1,n-1):
  A.append(A[-1]*(i+1)+per(i,i,mod))
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  if n-2-i==0:
    ans=ans+A[i]*Y[i]
  else:
    ans=(ans+A[i]*per(n-1,n-2-i,mod)*Y[i])%(10**9+7)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X[:-1]] #最後までの距離
Y = [(limit // i)%MOD for i in range(1, N)]
answer = 0
for x, y in zip(X, Y):
    answer += (x*y)%MOD
    answer %= MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X= [int(i) for i in input().split()]
lim = 10**9+7
def update(l):
    n = len(l)
    k = [0]*(n+1)
    k[0] = l[0]*(n+1)
    for i in range(1,n):
        k[i] = l[0] + l[i-1]*(i+1) + l[i]*(n-i)
    k[n] = l[0] + l[n-1]*(n+1)
    return k
def generate(n):
    if n == 1:
        return [1]
    else:
        l = [1]
        for _ in range(n-1):
            l = update(l)
        return l

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

M=generate(N-1)

ans = 0
for i in range(N-1):
    ans = (ans + (diff[i]*M[i]) % lim) % lim
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if j == n-1:
            ans += inv[n-1-i] * (x[j] - x[i]) % mod * fac[n-1] % mod
        else:
            ans += (inv[j-i] - inv[j-i+1]) * (x[j] - x[i]) % mod * fac[n-1] % mod
        ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def per(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r=n-r
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
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 )


n=int(input())
A=[1]
for i in range(1,n-1):
  A.append(A[-1]*(i+1)+per(i,i,mod))
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  if n-2-i==0:
    ans=ans+A[i]*Y[i]
  else:
    ans=(ans+A[i]*per(n-1,n-2-i,mod)*Y[i])%(10**9+7)
print(ans%mod)

Submission status: Time Limit Exceeded

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

def inv(x):
    return pow(x, MOD-2, MOD)
    
def C(n, r):
    return fact[n]//fact[r]//fact[n-r]

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

for i in range(1, N):
    fact.append(fact[-1]*i)
    
for i in range(N-1):
    for j in range(i+1, N):
        #print(i, j)
        
        r = j-i+1
        
        if j==N-1:
            r = N-2-i+1
            ans += (x[j]-x[i])*C(N-1, r)*fact[r-1]*fact[N-1-r]
            #print(C(N-1, r-1)*fact[N-1-r+1]*fact[r-2])
        else:
            r = j-i+1
            ans += (x[j]-x[i])*C(N-1, r)*fact[j-i-1]*fact[N-1-r]
        #print(x[j]-x[i])
            #print(C(N-1, r)*fact[N-1-r]*fact[r-2])
        #ans += (x[j]-x[i])*C(N-1, r)*fact[N-1-r]
        #print('ans:', ans)
        ans %= MOD

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X[:-1]] #最後までの距離
Y = [(limit // i)%MOD for i in range(1, N)]
answer = 0
for x, y in zip(X, Y):
    answer += (x*y)%MOD
    answer %= MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

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

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

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

show_flg=False
show_flg=True

ans=0


n=I()
x=LI()

cm=Comb(n+20)

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



St(n)

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

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

print(ans%mo)
#show(SSS)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

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

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

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

show_flg=False
show_flg=True

ans=0


n=I()
x=LI()
p=permutations(range(n-1))
cm=Comb(n+20)

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



St(n)

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

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

print(ans%mo)
#show(SSS)

Submission status: Time Limit Exceeded

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

def suraimu(n):
    dp=[[] for i in range(n)]
    dp[1].append(1)
    if n>2:
        for i in range(1,n-1):
            dp[i+1]=[(i+1)*j%mod for j in dp[i]]+[(dp[i][-1]*(i+1)+dp[i][0])%mod]
    return dp

z=suraimu(n)[-1]

ans=sum([z[i]*y[i] for i in range(n-1)])%mod
print(ans)

Submission status: Time Limit Exceeded

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

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

def mod_factional(n):
    if n <= 1:
        return 1
    # return (n * mod_factional(n - 1)) % (10 ** 9 + 7)
    return n * mod_factional(n - 1)

ans = 0
p = mod_factional(N - 1)
m = p
for i, (x, y) in enumerate(zip(xs, xs[1:])):
    tmp = y - x
    ans += tmp * m
    ans %= 10 ** 9 + 7
    p = p // (i + 2) * (i + 1)
    m += p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = np.array([last - x for x in X[:-1]]) #最後までの距離
Y = np.array([limit // i for i in range(1, N)])
Z = (X * Y)%MOD
answer = Z.sum()%MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = list(map(int, input().split()))
ans = 0
pattern = math.factorial(n-1)
p=1
k=pattern
while p < n:
  ans += k * (x[p]-x[p-1])
  ans %= 1000000007
  p += 1
  k += pattern//(p)
print(ans)

Submission status: Time Limit Exceeded

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

import sys

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
ans = 0
pattern = 1
for i in range(1, n):
  pattern *= i
p=1
k=pattern
while p < n:
  ans += k * (x[p]-x[p-1])
  ans %= 1000000007
  p += 1
  k += pattern//(p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7         # 問題に合わせて適宜書き換え
list_size = 252525    # 問題に合わせて適宜書き換え

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

N = int(input())
X = list(map(int,input().split()))
# print(f_list[N-1],f_r_list[N-1],(f_list[N-1]*f_r_list[N-1])%MOD)
ans = 0
for i in range(N):
    hoge = f_list[N-2]
    for j in range(i+1,N-1):
        piyo= (hoge*pow(j-i+1,MOD-2,MOD))%MOD
        hoge -= piyo
        ans += (X[j]-X[i])*piyo

        ans %= MOD
    ans += (X[-1]-X[i])*hoge
    ans %= MOD
print(ans)