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:
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    D = [0 for i in range(N)]

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

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

    ans = 0
    r = 0
    for i in range(1, N):
        r += n // i
        ans += D[i-1] * r
        ans %= 10**9+7
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)

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

print(ans%P)

Submission status: Time Limit Exceeded

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

fact = 1
for i in range(1, N):
    fact = fact * i

for i in range(N):
    ans = ans + (X[-1] - X[i]) * (fact // (i+1))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from math import factorial
n,*X=map(int,read().split())
last=X[-1]
X=[last-i for i in X[:-1]]
mod = 10**9+7
f=factorial(n-1)
s = sum(f//i*item for i,item in enumerate(X,1))
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(n - 1)]
 
fact_n_1 = math.factorial(n-1)

e = [None] * (n-1)
for i in range(n-1):
  if i == 0:
    e[i] = fact_n_1
  else:
    e[i] = e[i - 1] + fact_n_1 // (i + 1)

print(sum(e_i * d_i % 1000000007
          for i, (d_i, e_i) 
          in enumerate(zip(d, e))) % 1000000007 )

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
    for j in range(1,i+2):
        if i+1==j:
            dp[i3][j] = (dp[i2][j-1]*(i-0) + a)%MOD
        elif j==1:
            dp[i3][j] = (dp[i2][j]*(i-1) - a)%MOD
        else:
            dp[i3][j] = (dp[i2][j]*(i-j) + dp[i2][j-1] * (j-1))%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:
N = int(input())
x = list(map(int, input().split()))

mod = 10 ** 9 + 7
f = [1]
for i in range(1,N+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod

ans = 0
l = [0] + [(((comb(N-1,2+i) * f[N-(3+i)]) % mod) * f[i]) % mod for i in range(N-2)] + [f[N-2]]


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(1,n):
    p=0
    for j in range(1,i+1):
        p+=Fraction(1,j)
    ans+=(x[i]-x[i-1])*p
for k in range(1,n):
    ans=ans*k%(1000000000+7)
ans=ans%(1000000000+7)
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:

from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(1,n):
    p=0
    for j in range(1,i+1):
        p+=Fraction(1,j)
    ans+=(x[i]-x[i-1])*p
for k in range(1,n):
    ans=ans*k
ans=ans%(1000000000+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappop, heappush
import math

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

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

F = math.factorial(N-1)
t = 0
f = 0

for i in range(N-1):
    f += F // (i+1)
    x = X[i+1] - X[i]
    t += x * f

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

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:
N = int(input())
Xs = [0] + list(map(int, input().split()))
mod = 10**9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

NNN = (10**6)
g1 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

mxx = Xs[-1]
r = 0
for i in range(N):
    i += 1
    for j in range(1, N-i):
        ue = mul(g1[N-1], Xs[i+j] - Xs[i])
        ff = mul(mul(ue, inverse[j+1]), inverse[j])
        r = (r + ff) % mod
    ue = mul(g1[N-1], Xs[N]-Xs[i])
    ff = mul(ue,inverse[N-i])
    r = (r+ff)%mod

print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int,input().split()))
import numpy as np
import math
ans = 0
mod = 10**9+7
x=X[-1]
for i in range(N-1):
  for j in range(i+1,N-1):
    a = j-i-1
    ans += ((X[j]-X[i])%mod)*(math.factorial(a)%mod)*(math.factorial(N-1)%mod*pow(math.factorial(a+2),mod-2,mod))%mod
    
for k,y in enumerate(X[:N-1:]):
  a = N-k-2
  ans+=((x-y)%mod)*(math.factorial(a)%mod)*(math.factorial(N-1)%mod*pow(math.factorial(a+1),mod-2,mod))%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(n - 1)]
 
fact_n_1 = math.factorial(n-1)

e = {}
for i in range(n-1):
  if i == 0:
    e[i] = fact_n_1
  else:
    e[i] = e[i - 1] + fact_n_1 // (i + 1)

print(sum(e[i] * d_i % 1000000007
          for i, d_i 
          in enumerate(d)) % 1000000007 )

Submission status: Time Limit Exceeded

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

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

# def factional(n):
#     if n <= 1:
#         return 1
#     return n * factional(n - 1)

ans = 0
# p = factional(N - 1)
p = math.factorial(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
sys.setrecursionlimit(1000000)

n = int(input())
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(n - 1)]
 
def fact(m):
  return m * fact(m-1) if m != 1 else 1 

fact_n_1 = fact(n-1)

e = {}
for i in range(n-1):
  if i == 0:
    e[i] = fact_n_1
  else:
    e[i] = e[i - 1] + fact_n_1 // (i + 1)

print(sum(e[i] * d_i % 1000000007
          for i, d_i 
          in enumerate(d)) % 1000000007 )

Submission status: Time Limit Exceeded

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

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

def factional(n):
    if n <= 1:
        return 1
    return n * factional(n - 1)

ans = 0
p = 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


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    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


n = int(input())
xxx = list(map(int, input().split()))
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)

# print(factorials)
# print(invs)

ans = 0
dp = [0]
for i in range(n - 1):
    y = xxx[i + 1] - xxx[i]
    tmp = 0
    for k in range(i + 1):
        # print(' ', k, (dp[k] + factorials[k]) * invs[k])
        tmp = (tmp + (dp[k] + factorials[k]) * invs[k]) % MOD
    tmp = tmp * factorials[i] % MOD
    dp.append(tmp)
    # print(dp)
    ans = (ans + y * tmp * invs[i + 1]) % MOD
    # print(i, y, tmp, tmp * invs[i + 1] * factorials[n - 1] % MOD)
ans = ans * factorials[n - 1] % MOD
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

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

excnt = [0, 0]
for i in range(2, n):
    ex = cnt // i
    excnt.append(excnt[-1]+ex)


for i in range(1, n):
    l = X[i] - X[i-1]
    ans += l * (cnt + excnt[i])
    ans = ans % (10**9+7)

print(ans)

Submission status: Time Limit Exceeded

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

kai = [1]
tmp = 1
for i in range(1, n+1):
    tmp *= i
    tmp %= mod
    kai.append(tmp)
    
ans = 0
for i in range(1, n):
    tmp = 0
    for j in range(1, n-i+1):
        a = x[i+j-1] - x[i-1]
        a *= kai[n-1]
        if j != n-i:
            a *= kai[j-1]
            a *= pow(kai[j+1], mod-2, mod)
        else:
            a *= pow(j, mod-2, mod)
            a %= mod
        ans += a
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

ans = 0
for L in permutations(range(N-1), N-1):
  C = X.copy()
  for l in L:
    ans += C[l+1] - C[l]
    c = C[l]
    while C[l] == c:
      C[l] = C[l+1]
      l -= 1
print(ans % (10**9+7))

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
mod = 10**9 + 7
x = [i%mod for i in x]
# 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)
#print(n)
#print(x)

Submission status: Time Limit Exceeded

Solution code:
import math
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
k=10**9+5

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
x = list(map(int, input().split()))
 
def fact(m):
  return m * fact(m-1) if m != 1 else 1
 
d = [x[i+1] - x[i] for i in range(n - 1)]
fact_n_1 = fact(n-1)
print(sum(sum(fact_n_1 // (j + 1) 
              for j 
              in range(i + 1)) * d_i % 1000000007
          for i, d_i 
          in enumerate(d)) % 1000000007 )

Submission status: Time Limit Exceeded

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

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


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

ans = 0
for i in range(n-1):
    for j in range(i + 1, n-1):
        ans += ((x[j] - x[i]) * fact[n - 1] * inv_t[j - i + 1] * inv_t[j - i]) % mod
    ans += (x[n-1] - x[i]) * fact[n - 1] * inv_t[n-i-1]
    ans %= mod

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
import copy

N = int(input())
x = list(map(int, input().split()))
n = []
d = []

exp_len = 0

for i in range(N):
  n.append(i)

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

n_list = list(itertools.permutations(n[:-1]))

for i in range(math.factorial(N-1)):
  distance = copy.copy(d)
  for j in range(N - 1):
    if n_list[i][j] != 0:
      distance[n_list[i][j] - 1] += distance[n_list[i][j]]
    exp_len += distance[n_list[i][j]]

print(exp_len % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
class dist:
    def __init__(self,X,N):
        self.S = [0]*(N)
        l = list(range(N-1))
        for i in range(N-1):
            self.S[i+1] = self.S[i] + X[i+1] -X[i]
        self.L = itertools.permutations(l,N-1)

    def dist(self,left,right):
        return self.S[right]-self.S[left]

delta = 1000000007
N = int(input())
X = list(map(int,input().split()))
d = dist(X,N)
ans = 0
for l in d.L:
    slime = [1]*N
    for i in l:
        for j in range(i+1,N):
            if slime[j] == 1:
                ans += d.dist(i,j)
                if ans > delta:
                    ans = ans%delta
                slime[i] = 0
                break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: 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
mod = 10**9 + 7
# 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]) % mod
    #print("d={}".format(d))
    num_l.remove(k)
    #print("num_l={}".format(num_l))
    #print("--")
  sum_d += d
  #print("----")
print(sum_d)
#print(n)
#print(x)

Submission status: Time Limit Exceeded

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

kaijou = math.factorial(N-1)%(10**9+7)
ans=0
x=0
k=10**9+5

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

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

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

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

dif = [j - i for i, j in zip(st, st[1:])]

li = []
ho = 0
for i in range(1, n):
  d = 1
  for j in range(1, n):
    if j != i:
      d = (d * j) % MOD  
  ho += d
  li.append(ho)

ans = 0
for i, j in zip(dif, li):
  ans = (ans + (i % MOD) * (j % MOD)) % MOD 

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=list(map(int,input().split()))
m=1
i=0
k=0
s=0
j=0
while i<n-1:
	i+=1
	m*=i
while j<n-1:
	j+=1
	k+=m//j
	s+=k*(x[j]-x[j-1])	
print(s%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
x = LIST()
dist = [x[i+1]-x[i] for i in range(n-1)]
n -= 1

dp = [[0]*n for i in range(n)]
dp[1][0] = 1
dp[1][1] = 1
for i in range(2, n):
    dp[i][0] = dp[i-1][0] *i
    for j in range(i-1):
        dp[i][j+1] = dp[i-1][j+1] * (i+1)
    dp[i][i] = sum(dp[i-1][1:i]) + i*dp[i][0]

res = [0,] + dp[n-1][1:n]
ans = [res[i]+dp[n-1][0]*n for i in range(n)]
temp = sum([(ans[i] * dist[i])%MOD for i in range(n)])%MOD

print(temp)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
x = list(map(int,input().split()))
mod = 10 ** 9 + 7
dist = [[0]*N for _ in range(N)]
for i in range(N):
  for j in range(N):
    dist[i][j] = abs(x[j] - x[i]) % mod
#print(dist)
perm = list(itertools.permutations(list(range(N - 1))))
#print(perm)
ans = 0
for p in perm:
  tmp = list(p)
  tmp.append(N-1)
  for i in range(N - 1):
    ans += dist[tmp[i]][tmp[i+1]]% mod
    
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int,input().split()))
S = []
dp = [1]
mod = 10**9+7
for i in range(N):
    t = i+1
    dp.append(dp[i]*t)
ans = 0
for i in range(N-1):
    x = X[i]
    S.append(X[N-1]-x)
ans = 0
for i in range(N-1):
    x = S[i]
    t = i + 1
    ans += dp[N-1]//t*x%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

fac = math.factorial(n - 1)


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


res = 0
for i in range(n - 1):
    d = x[n - 1] - x[i]
    res += (d * fac * pow(i + 1, mod - 2)) % mod

print(res % mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = [int(i) for i in input().split()]
a = n*x[-1] - sum(x)
for i in range(2, n):
    a*=i
    if a>1000000007:
        a%=1000000007
for i in range(2, n):
    l = (x[-1] - x[i-1])*(i-1)
    for j in range(2, n):
        if j!=i:
            l*=j
            if l>1000000007:
                l%=1000000007
    a-=l
    a%=1000000007
print(int(a))

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

def F(i):
    return (limit // i)%MOD

def Z(s, t):
    return (s*t)%MOD

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 = [F(i) for i in range(1, N)]
answer = 0
for x, y in zip(X, Y):
    answer += Z(x, y)
    answer %= MOD

print(answer)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

dif = [j - i for i, j in zip(st, st[1:])]

li = []
ho = 0
for i in range(1, n):
  d = 1
  for j in range(1, n):
    if j != i:
      d = (d * j) % MOD  
  ho += d
  li.append(ho)

ans = 0
for i, j in zip(dif, li):
  ans += (i * j) % MOD 

print(ans % MOD)

Submission status: Time Limit Exceeded

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

ans = 0
ds1 = []
ds2 = []
for i in range(N-2, -1, -1):
    if i == N-2:
        ds1.append((X[N-1] - X[i]) % MOD)
    else:
        if ds1 == []:
            for d in ds2:
                for ii in range(i+1, N):
                    ds1.append((d + X[ii] - X[i]) % MOD)
            ds2 = []
        else:
            for d in ds1:
                for ii in range(i+1, N):
                    ds2.append((d + X[ii] - X[i]) % MOD)
            ds1 = []


print(sum(ds1) % MOD if ds2 == [] else sum(ds2) % MOD)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = list(map(int, input().split()))
import itertools
import numpy as np
mod = 10**9+7
Y = 0
Z = 0
n = 1

x = np.array(x)
w = np.diff(x)

A = len(list(itertools.permutations(w)))
for i in w:
    Y += A/n % mod
    Z += Y * i % mod
    n += 1
print(int(Z))

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
k=10**9+5

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import itertools
n=int(input())
x = list(map(int, input().split()))
last = x[-1]
p_list = list(itertools.permutations(x,n))
test = []
for i in range(n):
    if p_list[i][-1] == last:
        test.append(p_list[i])
sum = 0
for l in range(len(test)):
    for i in range(n-1):
        sum += abs(test[l][i]-test[l][i+1])
print(sum )

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 = []
    k.append((l[0]*(n+1)) % lim)
    for i in range(1,n):
        k.append((l[0] + l[i-1]*(i+1) + l[i]*(n-i)) % lim)
    k.append((l[0] + l[n-1]*(n+1))% lim)
    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]) % lim 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:
import sys

sys.setrecursionlimit(100001)

import math

denom = int(1e9+7)


def calc_coeff(n):
    if n == 1:
        return [1]
    elif n == 2:
        return[2,3]
    else:
        s = calc_coeff(n-1)
        ans = []
        #when first one is selected first
        ans.append(math.factorial(n) % denom)
        #otherwise
        for k in range(1,n-1):
            t = k*s[k-1] + (n-k-1)*s[k] + math.factorial(n-1) + s[k-1]
            ans.append(t % denom)
        t = (n-1)*s[n-2] + math.factorial(n-1) + s[n-2]
        ans.append(t % denom)
        return ans
    
    

N = int(input())
pos = [int(i) for i in input().split()]
x = []

coeff = calc_coeff(N-1)

tot = 0
for i in range(N-1):
    x.append(pos[i+1]-pos[i])
    tot += (coeff[i] * (pos[i+1]-pos[i])) % denom

print(tot % denom)

Submission status: Time Limit Exceeded

Solution code:
import math

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

MOD = 10 ** 9 + 7

diffList = [0] * (n - 1)
for i, position in enumerate(positionList):
  if i == 0:
    continue
  diffList[i - 1] = position - positionList[i - 1]

weightList = [0] * (n - 1)
for i in range(n - 1):
  for j in range(n - i - 1):
    weightList[i + j] += math.factorial(n - 1) // (i + 1)

result = 0
for i in range(n - 1):
  result = (result + diffList[i] * weightList[i]) % MOD
print(result)

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 = 2000
    # 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()))

ans = 0

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


for i in range(1, n):
    l = X[i] - X[i-1]
    excnt = 0
    for j in range(1, i):
        excnt += cnt//(j+1)
    ans += l * (cnt + excnt)
    ans = ans % (10**9+7)

print(ans)