Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

@lru_cache(maxsize=None)
def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    return (fib(n - 1) + fib(n - 2)) % MOD

def main():
    N ,M = cin.mapInt()
    A = cin.intColsList(M)

    for i in range(M - 1):
        if A[i + 1] - A[i] == 1:
            print(0)
            return
    if M == 0:
        print(fib(N))
        return
    A.insert(0,-1)
    A.append(N + 1)

    ans = 1
    for i in range(M + 1):
        n,m = A[i] + 1,A[i + 1] - 1,
        ans *= fib(m - n)
        ans %= MOD
    print(ans)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

def main():
    N ,M = cin.mapInt()
    A = [True] * (N + 1)
    for i in range(M):
        a = cin.int()
        A[a - 1] = False

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        if A[i] == True:
            dp[i + 1] = dp[i] + dp[i - 1]
            dp[i + 1] %= MOD
    print(dp[N])
    return

if __name__ == "__main__":
    main()
while True:
    num = input()
    if num == 0: break

    sht = []
    for i in range(num):
        sht.append(map(int, raw_input().split()))
        sht[i].append(sum(sht[i]))
        print " ".join(map(str, sht[i]))

    row = []
    for i in range(num + 1):
        sum = 0
        for j in range(num):
            sum += sht[j][i]
        row.append(sum)
    print " ".join(map(str, row))

### FIXED CODE ###

while True:
    num = input()
    if num == 0: break

    mrx = []
    row = [0] * (num + 1)
    for i in range(num):
        mrx.append(map(int, raw_input().split()))
        mrx[i].append(sum(mrx[i]))
        for j in range(num + 1): row[j] += mrx[i][j]
    mrx.append(row)
    for i in mrx: print "".join([str(s).rjust(5) for s in i])
l=[]
count=0
flg=0
n,k=map(int,input().split())
for i in range(1,n+1):
    l.append(i)
for i in range(1,len(l)):
    for j in range(i+1,len(l)+1):
        if j-i<=1:
            del l[j]
if k<=len(l):
    print("YES")
else:
    print("NO")



### FIXED CODE ###

l=[]
n,k=map(int,input().split())
for i in range(1,n+1,2):
    l.append(i)

if k<=len(l):
    print("YES")
else:
    print("NO")
def factorial(x):
    if x == 0:
        return 1
    return x * factorial(x - 1)

n, m = map(int, input().split())

dif = abs(n - m)
if dif >= 2:
    ans = 0
elif dif == 1:
    ans = factorial(n) * factorial(m) % (10**9 + 7)
else:
    ans = factorial(n) * factorial(m) * 2 % (10**9 + 7)

print(ans)

### FIXED CODE ###

"""
def factorial(x):
    if x == 0:
        return 1
    return x * fact(x - 1)
"""
from math import *
n, m = map(int, input().split())

dif = abs(n - m)
if dif >= 2:
    ans = 0
elif dif == 1:
    ans = factorial(n) * factorial(m) % (10**9 + 7)
else:
    ans = factorial(n) * factorial(m) * 2 % (10**9 + 7)

print(ans)
N,K= map(int,input().split())
H = list(map(int,input().split()))
H = sort(H)
s = 0
for i in range(N-K):
  s += H[i]
print(s+K)
  


### FIXED CODE ###

N,K= map(int,input().split())
H = list(map(int,input().split()))
H.sort()
s = 0
for i in range(N-K):
  s += H[i]
print(s)
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	u, v, w = list(map(int, input().split()))
	edges[u].append([v, w % 2])
	edges[v].append([u, w % 2])


bw = [-1 for i in range(n + 1)]
bw[1] = 0

def dfs(frm):
	for ne in edges[frm]:
		if bw[ne[0]] >= 0:
			continue
		else:
			bw[ne[0]] = abs(bw[frm] - ne[1])
			dfs(ne[0])

dfs(1)
for i in range(1, n + 1):
	print(bw[i])


### FIXED CODE ###

n, k = list(map(int, input().split()))
s = list(input())
d = {"A":"a", "B":"b", "C":"c"}
s[k-1] = d[s[k-1]]
print("".join(s))
import math
n=int(input())
t=[int(input()) for _ in [0]*n]

d=t[0]
print(d)
for i in range(1,n):
    d=(t[i]*d)//math.gcd(t[i],d)
    print(d)

### FIXED CODE ###

import fractions
n=int(input())
t=[int(input()) for _ in [0]*n]

d=t[0]
for i in range(1,n):
    d=(t[i]*d)//fractions.gcd(t[i],d)
print(d)
a,b=input().split()
a=int(a)
b=int(b)
print(a*b.2*(a+b))


### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b)
print(a*b,2*(a+b))
n=int(input())
xyh=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    if a[2]!=0:
        xyh.append(a)

for x in range(101):
    for y in range(101):
        p=0
        l=max(0,xyh[0][2]+abs(x-xyh[0][0])+abs(y-xyh[0][1]))
        for i in range(n):
            if l==max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1])):
                l=max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1]))
            else:
                p=1
                break
        if p==0:
            print(x,y,l)
            import sys
            sys.exit()
            



### FIXED CODE ###

n=int(input())
xyh=[]
h0=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    xyh.append(a)

from operator import itemgetter
xyh.sort(key=itemgetter(2))
xyh.reverse()

for x in range(101):
    for y in range(101):
        p=0
        l=max(0,xyh[0][2]+abs(x-xyh[0][0])+abs(y-xyh[0][1]))
        for i in range(n):
            if xyh[i][2]==0:
                if l>abs(x-xyh[i][0])+abs(y-xyh[i][1]):
                    p=1
                    break
                else:
                    continue
            if l==max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1])):
                l=max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1]))
            else:
                p=1
                break
        if p==0:
            print(x,y,l)
            import sys
            sys.exit()
import math
n = int(input())
wn = list(map(int, input().split()))


mini = math.inf
for i in range(n-1):
    new_mini = abs(sum(wn[:i]) -sum(wn[i:]))
    if new_mini < mini:
        mini = new_mini
print(mini)

### FIXED CODE ###

import math
 
n = int(input())
wn = list(map(int, input().split()))
 
mini = 10000000000
for i in range(n-1):
    new_mini = abs(sum(wn[:i+1]) -sum(wn[i+1:]))
    if new_mini < mini:
        mini = new_mini
print(mini)
n,x = map(int, input().split())
l = int(input())

d = 0
cnt = 0
for i in range(0, n):
  if i == 0:
    d = 0
  else:
    d = d + l
  if d <= x:
    cnt += 1
  if i != 0:
    l = int(input())

print (cnt)

### FIXED CODE ###

n,x = map(int, input().split())
l = [int(i) for i in input().split()]

d = 0
cnt = 0
for i in range(0, n + 1):
  if i == 0:
    d = 0
  else:
    d = d + l[i-1]
  if d <= x:
    cnt += 1

print (cnt)
import math

A,B,H,M = map(int,input().split())

x = 360//12
y = 360//60

a = M*y
b = (H+M/60)*x
T = 1
if a>=b:
  if a-b>180:
    k = 360 - a+b
  elif a - b == 180:
    print(A+B)
    T = 0
  else:
    k = a-b
else:
  if b-a>180:
    k = 360 - b+a
  elif b-a == 180:
    print(A+B)
    T = 0
  else:
    k = b-a
if T = 1:
  k = math.radians(k)

  ans = A*A + B*B - 2*A*B*math.cos(k)

  print(math.sqrt(ans))

### FIXED CODE ###

import math

A,B,H,M = map(int,input().split())

x = 360//12
y = 360//60

a = M*y
b = (H+M/60)*x
T = 1
if a>=b:
  if a-b>180:
    k = 360 - a+b
  elif a - b == 180:
    print(A+B)
    T = 0
  else:
    k = a-b
else:
  if b-a>180:
    k = 360 - b+a
  elif b-a == 180:
    print(A+B)
    T = 0
  else:
    k = b-a

if T == 1:
  k = math.radians(k)

  ans = A*A + B*B - 2*A*B*math.cos(k)

  print(math.sqrt(ans))
from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

#dp[i][w]
def main():
	n,w = map(int,input().split())
	wv = [list(map(int,input().split())) for i in range(n)]
	dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
	for i in range(1,n+1):
		cw = wv[i-1][0]
		cv = wv[i-1][1]
		for j in range(w+1):
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-cw] + cv) if j-cw >= 0 else dp[i-1][j]
	print(dp[-1][-1])

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

### FIXED CODE ###

from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

#dp[x][y] 最終日にyを選択した際のx日目までの最大の幸福度
def main():
	n = int(input())
	abc = [list(map(int, input().split())) for i in range(n)]
	dp = [[0,0,0]]
	for i in range(1,n+1):
		temp = []
		temp.append(max(dp[i-1][1], dp[i-1][2]) + abc[i-1][0])
		temp.append(max(dp[i-1][0], dp[i-1][2]) + abc[i-1][1])
		temp.append(max(dp[i-1][1], dp[i-1][0]) + abc[i-1][2])
		dp.append(temp)
	print(max(dp[-1]))

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()
import networkx as nx
import numpy as np

h, w, *X, = open(0).read().split()
h, w = int(h), int(w)

G = nx.grid_2d_graph(h, w)
for i, S in enumerate(X):
    for j, s in enumerate(S):
        if s == '#':
            G.remove_node((i, j))
try:
    path = nx.shortest_path(G, (0, 0), (h-1, w-1))
except NetworkXNoPath:
    print(-1)
else:
    for node in path:
        G.remove_node(node)
    print(len(G.nodes))

### FIXED CODE ###

import networkx as nx
import numpy as np

h, w, *X, = open(0).read().split()
h, w = int(h), int(w)

G = nx.grid_2d_graph(h, w)
for i, S in enumerate(X):
    for j, s in enumerate(S):
        if s == '#':
            G.remove_node((i, j))
try:
    path = nx.shortest_path(G, (0, 0), (h-1, w-1))
except nx.NetworkXNoPath:
    print(-1)
else:
    for node in path:
        G.remove_node(node)
    print(len(G.nodes))
n = int(input())
a = list(map(int, input().split(' ')))
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [500001]
    R = a[mid:right] + [500001]
    i=0
    j=0
    for k in range(left, right):
        counter += 1
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

def mergeSort(a, left, right):
    if(left+1 < right):
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

mergeSort(a, 0, n)
#print(" ".join([str(i) for i in a]))
print(*a)
print(counter)



### FIXED CODE ###

import math
sentinel = 1e9 + 1
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [sentinel]
    R = a[mid:right] + [sentinel]
    i,j = 0,0
    for k in range(left, right):
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
    counter += right - left
def mergeSort(a, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)


n = int(input())
a = list(map(int, input().split()))
mergeSort(a, 0, n)
print(*a)
print(counter)
a = input().split()
return int(a[0]) + int(a[2]) if a[1] == "+" else int(a[0]) - int(a[2])

### FIXED CODE ###

a = input().split()

if a[1] == "+":
  print(int(a[0]) + int(a[2]))
else:
  print(int(a[0]) - int(a[2]))
N=int(input())
Y=int(input())

a=-1
b=-1
c=-1
for i in range(0,N+1):
    for j in range(0,N-i+1):
        if 10000*i+5000*j+1000*(N-i-j)==Y:
            a=i
            b=j
            c=N-i-j
            break
                            
print(a,b,c)
    

### FIXED CODE ###

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

a=-1
b=-1
c=-1
for i in range(0,N+1):
    for j in range(0,N-i+1):
        if 10000*i+5000*j+1000*(N-i-j)==Y:
            a=i
            b=j
            c=N-i-j
            break
                            
print(a,b,c)
n,k=map(int,input().split())
ab=[[int(i) for i in input().split()]for j in range(n)]
dic={}
for a,b in ab:
    if a in dic:
        dic[a]+=j
    else:
        dic[a]=j
dic=sorted(dic.items() , key=lambda x:x[0])
check=0
for i,j in dic:
    check+=j
    if check>=k
    print(i)
    break

### FIXED CODE ###

n,k=map(int,input().split())
ab=[[int(i) for i in input().split()]for j in range(n)]
dic={}
for a,b in ab:
    if a in dic:
        dic[a]+=b
    else:
        dic[a]=b
dic=sorted(dic.items() , key=lambda x:x[0])
check=0
for i,j in dic:
    check+=j
    if check>=k:
        print(i)
        break
import sys
import itertools
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from math import ceil, floor, sqrt #小数点切り上げ、切り捨て、平方根
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque #要素ごとの出現回数、双方向アクセス可能データ型
import heapq
import numpy as np
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
# template


n = int(input())
h = list(map(int, input().split()))
# h = [int(x) for x in input().split()]

inf = 1e8
dp = [inf] * n
dp[0] = 0

for i in (0, n):
    dp[i+1] = max(dp[i+1], dp[i] + abs(h[i] + h[i+1]))
    dp[i+2] = max(dp[i+2], dp[i] + abs(h[i] - h[i+2]))

print(dp[-1])



### FIXED CODE ###

import sys
import itertools
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from math import ceil, floor, sqrt, isinf #小数点切り上げ、切り捨て、平方根
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque #要素ごとの出現回数、双方向アクセス可能データ型
import heapq
import numpy as np
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
# template


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

dp = [1e9] * n

dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if(i > 1):
         dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

print(dp[-1])
A,B=map(int,input())
A=A*B
print(A)

### FIXED CODE ###

A,B=map(int,input().split())
A=A*B
print(int(A))
from collections import deque
n,k=[int(i) for i in input().split()]
D=deque()
h=[int(i) for i in input().split()]
for i in h:
    D.append(i)   
maxnum=0
times=min(n,k)
for limit in range(times):
    for a in range(limit+1):
        get=[]
        Dcopy=D[:]
        b=limit-a
        for i in range(a):
            get.append(Dcopy.popleft())
        for i in range(b):
            get.append(Dcopy.pop())
        get.sort(reverse=True)
#         print(get)
        for i in range(times-limit):
            if len(get)==0:
                break
            if get[-1]>=0:
                break
            get.pop()
        sumnum=0
        for i in get:
            sumnum+=i
        if sumnum>maxnum:
            maxnum=sumnum
print(maxnum)

### FIXED CODE ###

#デックをインポート
from collections import deque

#前準備
n,k=[int(i) for i in input().split()]

#デックを用意
D=deque()
h=[int(i) for i in input().split()]
for i in h:
    D.append(i)   
    
#答え
maxnum=0

#繰り返す単位
times=min(n,k)

#aとbの操作の合計のlimitを設定
for limit in range(times+1):
#     print(D)
    
    #aの操作を決定
    for a in range(limit+1):
        get=[]
        Dcopy=deque()
        for i in range(n):
            Dcopy.append(D[i])
        b=limit-a
        for i in range(a):
            get.append(Dcopy.popleft())
        for i in range(b):
            get.append(Dcopy.pop())
        get.sort(reverse=True)
#         print(get)
        for i in range(k-limit):
            if len(get)==0:
                break
            if get[-1]>=0:
                break
            get.pop()
        sumnum=0
        for i in get:
            sumnum+=i
        if sumnum>maxnum:
            maxnum=sumnum
            
#         print(a,b,Dcopy,get,sumnum)
print(maxnum)
N, K = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
loop = []
start = 0
index = 0
check = [-1] * N
fin = False
count = 0
while True:
    if check[index] != -1:
        start = check[index]
        break
    else:
        loop.append(index)
        if len(loop) == K + 1:
            print(index + 1)
            sys.exit()
        check[index] = count
        count += 1
        index = a[index]


if (K + 1 - start) % len(loop[start:]) == 0:
    print(loop[-1] + 1)
else:
    print(loop[start + (K + 1 - start) % len(loop[start:]) - 1] + 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
loop = []
start = 0
index = 0
check = [-1] * N
fin = False
count = 0
while True:
    if check[index] != -1:
        start = check[index]
        break
    else:
        loop.append(index)
        if len(loop) == K + 1:
            print(index + 1)
            fin = True
            break
        check[index] = count
        count += 1
        index = a[index]

if not fin:  # len(loop)<=K
    if (K + 1 - start) % len(loop[start:]) == 0:
        print(loop[-1] + 1)
    else:
        print(loop[start + (K + 1 - start) % len(loop[start:]) - 1] + 1)
import sys
import itertools
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ls = [0] + list(map(lambda x: int(x) - 1, input().rstrip('\n').split()))
    ls = [i % k for i in list(itertools.accumulate(ls))]
    print(ls)

    d = collections.defaultls):
        t += d[x]
        d[x] += 1
        if i >= k - 1:
            d[ls[i - k + 1]] -= 1
    print(t)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import itertools
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ls = [0] + list(map(lambda x: int(x) - 1, input().rstrip('\n').split()))
    ls = [i % k for i in list(itertools.accumulate(ls))]
    
    d = collections.defaultdict(int)
    t = 0
    for i, x in enumerate(ls):
        t += d[x]
        d[x] += 1
        if i >= k - 1:
            d[ls[i - k + 1]] -= 1
    print(t)


if __name__ == '__main__':
    solve()
import numpy as np
import math
import sys
readline = sys.stdin.buffer.readline
MOD = 10**9+7

N = int(readline())
x = np.array(readline().split(), dtype=np.int64)
# print(N, x)

# dif = np.zeros((N-1,N-1), dtype=np.int64)
dif = np.fmax(x[1:].reshape(-1, N-1) - x[:N-1].reshape(N-1, -1), 0)
# print(dif)

cnt = np.zeros((N-1,N-1), dtype=np.int64)
for i in range(N-1):
    for j in range(i+1):
        if i == 0:
            cnt[N-2-i, N-2-j] = math.factorial(N-1)
        elif j == 1:
            cnt[N-2-i, N-2-j] = cnt[N-2-i+1, N-2-j+1] // (i+1)
        elif j == 0:
            cnt[N-2-i, N-2-j] = cnt[N-2-i+1, N-2-j] * i // (i+1)
        else:
            cnt[N-2-i, N-2-j] = cnt[N-2-i+1, N-2-j+1]
# print(cnt)

ans = np.mod((dif * cnt), MOD)
# print(ans)
ans = ans.sum() % MOD
print(ans)


### FIXED CODE ###

MOD = 10**9+7

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

ans = 0
mul = 0
for i in range(N-1):
    mul += pow(i+1, MOD-2, MOD)
    ans += (x[i+1] - x[i]) * mul % MOD
    ans %= MOD
for i in range(2, N):
    ans *= i
    ans %= MOD
print(ans)