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: Wrong Answer

Solution code:
from collections import defaultdict
import sys
def main():
    sys.setrecursionlimit(10**9)
    def loopcalc(a,b):
        z = d[(a,b)]
        if z:
            return z
        else:
            tmp = 0
            for j in range(a+1,b):
                tmp += loopcalc(a,j)*kj[b-j-1]+loopcalc(j,b)*kj[j-a-1]
                tmp = tmp%dv
            tmp += loopcalc(a+1,b)+(x[b]-x[a])*kj[b-a-2]
            tmp = tmp%dv
            d[(a,b)] = tmp
            return tmp
    
    n = int(input())
    x = list(map(int,input().split()))
    ans = 0
    dv = 10**9+7
    kj = [1]
    for i in range(2,n+1):
        kj.append(kj[-1]*i)
    d = defaultdict(int)
    for i in range(n-1):
        d[(i,i+1)] = x[i+1]-x[i]
    ans = loopcalc(0,n-1)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

X = [X[i] - X[0] for i in range(N)]

mod = 1000000007

total = sum(X)
d = [X[i+1] - X[i] for i in range(N-1)]
ans = 0
cross = 1

for i in range(N):
    ansi = (total * cross) % mod
    ans += ansi % mod
    if(i != N - 1):
        total -= d[0] * (N - i - 1)
    cross *= i+2

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
m=1
for i in range(2,n):m=m*i%mod
def m_b(b):return m*pow(b,mod-2,mod)%mod
ans=0
x=0
y=0
for i in range(n-1):
  x+=m-y
  x%=mod
  y+=m_b(n-i-1)
  y%=mod
  ans+=x*(a[i+1]-a[i])
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
def modinv2(a,m):
    return pow(a,m-2,m)

def f(n,m):
    a = 1
    for i in range(2,n+1):
        a = a*i%m
    return a

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

ans = 0
P = 10**9+7

b = f(N-1,P)
#print(b)

for i in range(N-1):
    l = 0
    c = modinv2(N-1-i,P)
    #print(c)
    for j in range(i+1,N):
        l += x[j]-x[i]
        l %= P
    #print(l)
    l = l*b%P
    l = l*c%P
    ans += l

print(ans%P)

Submission status: Wrong Answer

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

l = [0]*(N-1)
for i in range(0,N-1):
    l[i] = x[i+1]-x[i]

print(l)
total = 0

for i in range(0,N-1):
    poyo = 1
    for j in range(0,N-1):
        if i != j:
            poyo = poyo * (j+1) % mod
        
    total = (total + poyo*l[i]*(2*(i+1)-1)) % mod
 
print(total)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

X = [X[i] - X[0] for i in range(N)]

mod = 1000000007

total = sum(X)
d = [X[i+1] - X[i] for i in range(N-1)]
ans = 0

for i in range(N):
    ansi = (total * (i + 1)) % mod
    ans += ansi % mod
    if(i != N - 1):
        total -= d[0] * (N - i - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools

n=int(input())
x = list(map(int, input().split()))
y = list(itertools.accumulate(x))
ans=0
mod=10**9+7
v=sum(x)-x[0]*n

for i in range(n-1):
    if i==0:
        ans+=(v)*math.factorial(n-1)//(n-1-i)
    else:
        v-=(n-i)*(x[i]-x[i-1])

        ans += (v) * math.factorial(n - 1) // (n - 1 - i)
        ans%=mod




print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
X = list(map(int, input().split()))
Y = [1]
# for i in range(N - 1):
#     Y.append(X[i + 1] - X[i])

Z = [1]
f = 1
count = 0
N_F = math.factorial(N - 1)
for i in range(1, N):
    try:
        Y.append(X[i + 1] - X[i])
    except:
        Z.append(Z[i - 1] * (i + 1) + math.factorial(i))
        count += Z[i - 1] * N_F // math.factorial(i) * Y[i - 1]
        continue
    Z.append(Z[i - 1] * (i + 1) + math.factorial(i))
    count += Z[i - 1] * N_F // math.factorial(i) * Y[i - 1]

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

Submission status: Wrong Answer

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

X = [X[i] - X[0] for i in range(N)]

mod = 1000000007

total = sum(X)
d = [X[i+1] - X[i] for i in range(N-1)]
ans = 0

print(total)
for i in range(N):
    ansi = (total * (i + 1)) % mod
    ans += ansi % mod
    if(i != N - 1):
        total -= d[0] * (N - i - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import functools
N = int(input())
x = [int(i) for i in input().split()]
mod = 10**9+7
start = 1
st = 1
st_list = [0] * N
for i in range(N-1):
    st *= i+1
    st %= mod
    st_list[i] = st
all_dis = 0
for i in range(N-1):
    far = x[i+1]-x[i]
    all_dis += far*start*st_list[N-2]//st_list[i]
    start = start*(i+2)+st_list[i]%mod
    all_dis %= mod
print(all_dis)

Submission status: Wrong Answer

Solution code:
n=int(input())
X=[int(i) for i in input().split()]
mod=10**9+7
n_max=2*10**5
F=[0]*(n_max+1)
F[0]=1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod

ans=0
DP=[[0]*n for _ in range(n)]
for i in range(1,n):
  for j in range(1,i+1):
    if j==1:
      DP[i][j]=F[i-1]
    elif j==i:
      DP[i][j]=1
    else:
      DP[i][j]=DP[i-1][j-1]+(i-1)*DP[i-1][j]
  for j in range(1,i+1):
    ans=(ans+j*DP[i][j]*(X[i]-X[i-1])*F[n-1]//F[i])%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy
import bisect
import numpy as np

N=int(input())
x = list(map(int,input().split()))
dp = [[0]*(N+2) for _ in range(N+2)]
dp[1][0] = -1
dp[1][1] = -1
dp[1][2] = 1
MOD = 10**9+7
for i in range(2,N):
    for j in range(1,i+2):
        if i+1==j:
            dp[i][j] = (dp[i-1][j-1]*(i-0) + 1)%MOD
        elif j==1:
            dp[i][j] = (dp[i-1][j]*(i-1) - 1)%MOD
        else:
            #dp[i][j] = dp[i-1][j-1]*(j-1) + dp[i-1][j-2] * (i-j-1)
            dp[i][j] = (dp[i-1][j]*(i-j) + dp[i-1][j-1] * (j-1))%MOD
    print(dp[i])
res = 0
for i in range(N):
    res += dp[N-1][i+1]*x[i]
#for i in range(1,N):
#    res = (res*i)%MOD
print(res%MOD)

Submission status: Wrong Answer

Solution code:

n = int(input())
x = [int(x) for x in input().split()]
inf = 10**9+7
a = 1
for i in range(n-1, 0, -1):
    a *= i
    a %= inf
key = 0
ans = 0
for i in range(n-1):
    key += a//(i+1)
    key %= inf
    ans += key*(x[i+1]-x[i])
    ans %= inf
    

print(ans)

Submission status: Wrong Answer

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
  
inv=[1]*(N+1)
inv[-1]=pow(upp[-1], MOD-2, MOD)
for i in range(N, 1, -1):
  inv[i-1]=inv[i]*(i)

#a=[0]*(N-1)
#a[0]=upp[N-1]
#for i in range(1, N-1):
#  a[i]=a[0]*inv[i+1]
#  a[i]%=MOD

a=[0]*(N-1)
a[0]=upp[N-1]
for i in range(1, N-1):
  a[i]=a[0]//(i+1)

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]
    out%=MOD
  return out

ex=moddot(b, y)
print(ex)

Submission status: Wrong Answer

Solution code:
N = int(input())
tmp = input().split()
x = [i for i in tmp]
print(x)

Submission status: Wrong Answer

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

kai = 1
for i in range(n-2):
    kai = kai*(i+2)
    kai = kai%mo 

rui = []
tmp = 0
for i in range(n-1):
    tmp += d[-i-1]
    tmp = tmp%mo
    rui.append(tmp)

#print(d)
#print(kai)
#print(rui)

ans = 0
for i in range(n-1):
    #print(kai/(n-i-1))
    fa = kai//(n-i-1)
    fa = ( (fa%mo)*(rui[i]%mo) )%mo
    ans += fa
    ans = ans%mo

print(ans%mo)

Submission status: Wrong Answer

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)

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: Wrong Answer

Solution code:
N = int(input())
a = list( map(int, input().split() ) )
kai = 1
M = 10**9+7
result = 0
for i in range(1,N):
    kai *= i

kai = kai%M
for i in range(N-1):
    result += kai * (a[N-1] - a[i]) // ( i+1 )

print( result%M )

Submission status: Wrong Answer

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
L *= n_1

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
X = list(map(int, input().split()))
Y = []
for i in range(N - 1):
    Y.append(X[i + 1] - X[i])

Z = [1]
f = 1
for i in range(1, N):
    Z.append(Z[i - 1] * (i + 1) + math.factorial(i))

N_F = math.factorial(N - 1)
count = 0
for i in range(N - 1):
    print(Z[i] * N_F // math.factorial(i + 1))
    count += Z[i] * N_F // math.factorial(i + 1) * Y[i]
print(count % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD=10**9+7
N=int(input())
x=list(map(int, input().split()))
y=np.array([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
  
inv=[1]*(N+1)
inv[-1]=pow(upp[-1], MOD-2, MOD)
for i in range(N, 1, -1):
  inv[i-1]=inv[i]*(i)

a=[0]*(N-1)
a[0]=upp[N-1]
for i in range(1, N-1):
  a[i]=a[0]//(i+1)
  
a=np.array(a)
a%=MOD

ex=np.dot(a, y)
for i in range(1, N-1):
  ex+=np.dot(a[:-i], y[i:])
  ex%=MOD
  
print(ex)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())

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

mod = 10**9 + 7

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

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

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

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

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

ans = 0

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

print(dp[-1] % mod)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
x=list(map(int,input().split()))
if n>2000:
  sys.exit()
mod=10**9+7
l=[]
l2=[1 for i in range(n-1)]
for i in range(n-1):
  l.append(x[i+1]-x[i])
for i in range(1,n):
  for j in range(n-1):
    if i!=j+1:
      l2[j]*=i
      l2[j]%=mod
l3=[]
l3.append(l2[0])
for i in range(n-2):
  l3.append(l3[-1]+l2[i+1])
ans=0
for i in range(n-1):
  ans+=l3[i]*l[i]
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

import numpy as np

# In[]:
N = inp()
xx = inpl()

# N = 3
# xx = 1,2,3

# In[]:
aa = np.array([1], dtype=np.uint64)
fac = 1
for L in range(2,N):
    fac = fac*(L-1)%mod
    naa = np.array([fac]*L, dtype=np.uint64)
    naa[:L-1] += np.arange(L-1,0,-1, dtype=np.uint64) * aa
    naa[1:]   += np.arange(2,L+1, dtype=np.uint64) * aa
    naa %= mod
    aa = naa[:]
    # print(aa)

# print(aa)

# In[]:
dx = np.array([xx[i]-xx[i-1] for i in range(1,N)],dtype=np.uint64)
# print(dx)

# In[]:
ans = sum(aa*dx)%mod
print(int(ans))

Submission status: Wrong Answer

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) % MOD
last = X[-1]
X = [last - x for x in X] #最後までの距離
answer = 0
for i in range(1, N):
    answer += X[i-1] * limit // i
    answer %= MOD

print(answer)

Submission status: Wrong Answer

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

kai = 1
for i in range(n-2):
    kai = kai*(i+2)
    kai = kai%mo 

rui = []
tmp = 0
for i in range(n-1):
    tmp += d[-i-1]
    tmp = tmp%mo
    rui.append(tmp)

#print(d)
#print(kai)
#print(rui)

ans = 0
for i in range(n-1):
    #print(kai/(n-i-1))
    fa = kai//(n-i-1)
    fa = (fa*rui[i])%mo
    ans += fa

print(ans%mo)

Submission status: Wrong Answer

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

print(int(sum(x)- x[0]) % 1000000007)

Submission status: Time Limit Exceeded

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


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

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

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

    print(ans)
    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

answer=0
for i in range(N-1):
  for j in range(i+1,N-1):
    ji_inv=inv_table[j-i]
    ji1_inv=inv_table[j-i+1]
    term=(ji_inv*ji1_inv)%MOD
    answer+=term*(xlist[j]-xlist[i])
    answer%=MOD
    #print(i,j,term)
  
  ni_inv=inv_table[N-1-i]
  term=ni_inv%MOD
  answer+=term*(xlist[N-1]-xlist[i])
  answer%=MOD
  #print(i,N-1,term)
  
answer*=fact_nm1
answer%=MOD  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7

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

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

answer=0
for i in range(N-1):
  for j in range(i+1,N-1):
    ji_inv=pow(j-i,MOD-2,MOD)
    ji1_inv=pow(j-i+1,MOD-2,MOD)
    term=(fact_nm1*ji_inv*ji1_inv)%MOD
    answer+=term*(xlist[j]-xlist[i])
    answer%=MOD    
    #print(i,j,term)
  
  ni_inv=pow(N-1-i,MOD-2,MOD)
  term=(fact_nm1*ni_inv)%MOD
  answer+=term*(xlist[N-1]-xlist[i])
  answer%=MOD
  #print(i,N-1,term)
  
print(answer)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

va, vb = 0, 1
ans = 0

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


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import Fraction
from math import factorial

rl = sys.stdin.readline


def solve():
    N = int(rl())
    x = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    acc = [Fraction(0)] * N
    for i in range(1, N):
        acc[i] = acc[i - 1] + Fraction(1, i)
    
    ans = 0
    for i in range(N - 1):
        ans = ans + (x[i + 1] - x[i]) * acc[i + 1] % MOD
    
    ans = int(ans * factorial(N - 1) % MOD)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i + 1] = self.factorial[i] * (i + 1) % mod
        self.inv[n] = pow(self.factorial[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def fact(self, m):
        return self.factorial[m]

    def invfact(self, m):
        return self.inv[m]


MOD = 10**9 + 7

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

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

F = Factorial(N + 1, MOD)

res = 0
f = 0

for i in range(N - 1):
    f = (i + 1) * f + F.fact(i)
    res += D[i] * f * F.invfact(i + 1) * F.fact(N - 1)
    res %= MOD

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
N=int(input())
X=list(map(int,input().split()))
lastX=X.pop()
mod=10**9+7
ferumaC=10**5+1
fac=[1,1]
for i in range(2,ferumaC):
    fac.append(fac[i-1]*i%mod)
ipow=[pow(i,mod-2,mod) for i in range(ferumaC)]
count=0
for i in range(1,len(X)):
    count2=0
    for n in range(min(i,len(X)-i)):
        a=((len(X)-1)//i)*i+n
        if a>len(X)-1:
            a-=i
        #print(n,a,i)
        count2+=X[a]-X[n]
    count=(count+ipow[i+1]*ipow[i]*count2)%mod
for i in range(len(X)):
    count=(count+(lastX-X[i])*ipow[len(X)-i])%mod
count=count*fac[N-1]%mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
N=int(input())
X=list(map(int,input().split()))
lastX=X.pop()
mod=10**9+7
ferumaC=10**5+1
fac=[1,1]
for i in range(2,ferumaC):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]
ipow=[pow(i,mod-2,mod) for i in range(ferumaC)]
count=0


for i in range(1,len(X)):
    count2=0
    for n in range(min(i,len(X)-i)):

        a=((len(X)-1)//i)*i+n
        if a>len(X)-1:
            a-=i

        #print(n,a,i)
        count2+=X[a]-X[n]


    count=(count+ipow[i+1]*ipow[i]*count2)%mod
for i in range(len(X)):
    count=(count+(lastX-X[i])*ipow[len(X)-i])%mod
count=count*fac[N-1]%mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = list(map(int,input().split()))
dp = [[0]*(N+2) for _ in range(3)]
dp[1][0] = -1
dp[1][1] = -1
dp[1][2] = 1
a = 1
MOD = 10**9+7
for i in range(2,N):
    a = (a*(i-1))%MOD
    i2 = (i+2)%2+1
    i3 = (i+1)%2+1
    dp[i3][1] = (dp[i2][1]*(i-1) - a)%MOD
    for j in range(2,i+1):
        dp[i3][j] = (dp[i2][j]*(i-j) + dp[i2][j-1] * (j-1))%MOD
    dp[i3][i+1] = (dp[i2][i]*i + a)%MOD
res = 0
n = (N-2)%2+1
for i in range(N):
    res += (dp[n][i+1]*x[i])%MOD
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction as Frc
import math

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

n = int(input())
slime = [int(x) for x in input().split()]

md = 10 ** 9 + 7
fct = math.factorial(n - 1) % md
ans = 0
fr = Frc(1, 1)
for i in range(n - 1):
    c = fr.numerator % md
    p = fr.denominator % md
    ans = (ans + fct * modinv(p, md) * c % md * (slime[i + 1] - slime[i]) % md) % md
    fr += Frc(1, i + 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction as Frc
import math

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

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

    return (m+x%m)%m
n = int(input())
slime = [int(x) for x in input().split()]

md = 10 ** 9 + 7
fct = math.factorial(n - 1) % md
ans = 0
fr = Frc(1, 1)

for i in range(n - 1):
    c = fr.numerator
    p = fr.denominator

    ans = (ans + fct * (slime[i + 1] - slime[i]) % md * c % md * mod_inv(p,md) ) % md
    fr += Frc(1, i + 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

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

n = int(input())
slime = [int(x) for x in input().split()]
md = 10**9+7
fct = math.factorial(n-1) % md
aa = 0
for i in range(n-1):
    for j in range(i+1,n):
        buf_c = j - i - 1
        buf_p = j - i + 1
        if j == n - 1:
            buf_p -= 1
        if buf_c == 0:
            buf_c = 1
        buf_sum = fct * math.factorial(buf_c) % md
        buf_sum = buf_sum * mod_inv(math.factorial(buf_p), md)
        aa += (buf_sum * (slime[j] - slime[i])) % md
        aa %= md
print(int(aa))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = list(map(int, input().split()))
def xx(a):
    if a == 1:
        return [1] 
    else:
        b = [1]
        z = 1
        for i in range(2, a+1):
            z *= (i-1)
            for j in range(len(b)):
                b[j] *= i
            b.append(b[len(b)-1] + z)
        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:
n=int(input())
A=list(map(int,input().split()))
mod = 10**9 + 7
# (N-1)!を求める
fac=1
for i in range(1,n):
  fac = fac*i
# 個数テーブルを準備する
cnt=[0]*n
for i in range(1,n):
  cnt[i] = fac // i
  cnt[i] = (cnt[i]+cnt[i-1])
# 計算
ans=0
for i in range(n-1):
  ans += (A[i+1]-A[i]) * cnt[i+1]

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
factorials = [1] + list(accumulate(range(1,n + 1), mul))

combinations = dict()
def combination(i, j):
    j = min(j, i - j)
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    t = factorials[n] // i
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
factorials = [1] + list(accumulate(range(1,n + 1), mul))

combinations = dict()
def combination(i, j):
    j = min(j, i - j)
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    t = factorials[lt] * combination(n, gt) * factorials[gt]
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import count, accumulate
from operator import mul
from functools import reduce
lines = sys.stdin.readlines()

positions = [int(i) for i in lines[1].split(' ')]

distances = [ j - i for i, j in zip(positions, positions[1:])]

n = len(distances)
factorials = [1] + list(accumulate(range(1,n + 1), mul))

combinations = dict()
def combination(i, j):
    if (i, j) in combinations:
        return combinations((i, j))
    else:
        return factorials[i] // (factorials [j] * factorials[i - j])

permutations = dict()
def permutation(i, j):
    if (i, j) in permutations:
        return permutations((i, j))
    else:
        return reduce(mul, range(j, i+1))

s = 0
result = 0
for d, i in zip(distances, count(1)):
    lt = i - 1
    gt = n - i
    t = factorials[lt] * combination(n, gt) * factorials[gt]
    s += t
    result += d * s

print(int(result % (pow(10,9) + 7)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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()))
ans=0
for i in range(n-1):
    t = (x[n-1]-x[i])%P
    o =(fac[i]*fac[n-2-i])%P
    g = (comb(n-1,n-1-i)*o)%P
    t = (t * g)%P
    ans=(ans+t)%P

for i in range(n-1):
    for j in range(i+1,n-1):
        t = (x[j]-x[i])%P
        o =(fac[n-1-j+i-1]*fac[j-i-1])%P
        g = (comb(n-1,j-i+1)*o)%P
        t = (t * g)%P
        ans=(ans + t)%P
print(ans%P)