Harryxun/stf_run huggingface dataset:
n = int(input())
p = list(map(int, input().split()))

cnt = 0
for i in range(1, n):
    if (p[i] - p[i - 1] > 0 and p[i + 1] - p[i] >= 0) or (p[i] - p[i - 1] <= 0 and p[i + 1] - p[i] < 0):
        print("==", i, "==")
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
for i in range(1, n - 1):
    if (p[i] - p[i - 1] > 0 and p[i + 1] - p[i] >= 0) or (p[i] - p[i - 1] <= 0 and p[i + 1] - p[i] < 0):
        cnt += 1
print(cnt)
from scipy.sparse.csgraph import floyd_warshall

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

ans=0
for i in range(m):
    ll=l[:i]+l[i+1:]

    d=[[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i]=0

    for j in ll:
        d[j[0]-1][j[1]-1]=1
        d[j[1]-1][j[0]-1]=1

    d=floyd_warshall(d)

    if float('inf') in d:
        ans+=1

print(ans)

### FIXED CODE ###

from collections import deque

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

def make_dict(x,y):
    for i in ll:
        if i[x] in d.keys():
            d[i[x]]+=[i[y]]
        else:
            d[i[x]]=[i[y]]

cnt=0
for i in range(m):
    ll=l[:i]+l[i+1:]
#    print(ll)
    d={}
    make_dict(0,1)
    make_dict(1,0)
#    print(d)
    k_l=list(d.keys())
    v_l=list(d.values())
#    print(k_l)

    x=0
    sk=k_l[x]
    dq=deque()
    dq.append(sk)
#    while dq:
#    print(dq)
#    x=0
    seen=[]
    while dq:
#    while n<10:
        k=dq.pop()
        k_ll=d[k]
        seen.append(k)
#        print(k_ll)
        for i in k_ll:
            if i not in seen:
                dq.append(i)
#        d=d.pop(sk)
#        print(dq)
        x+=1
#    print(set(seen),len(set(seen)))
    if len(set(seen))!=n:
        cnt+=1
print(cnt)
N=int(input())
b=0

def f(N):
	if N<2:
		return 1
	if N>=2:
		return N*f(N-2)
X=f(N)
print(X)
if X%2==0:
	while X%5==0:
		X=X/5
		b=b+1
      
print(b)

### FIXED CODE ###

import math
N=int(input())
a=0
b=10
if N%2!=0:
	print(0)
else:
	while N>=b:
		a+=(N//b)
		b=b*5
	print(a)
K=int(input(""))
S=input("")
lenS=len(S)
if lenS<=K:
  print(S)
else:
  print(S[:K]+"...")

### FIXED CODE ###


N=int(input(""))
x=N%10
if x==3:
  print("bon")
elif x==0 or x==1 or x==6 or x==8:
  print("pon")
else:
  print("hon")
s = input()
k = int(input())

if int(s[0]) == 1:
  one_count = 0
  i = 0
  while int(s[i]) == 1:
    one_count += 1
    i += 1
  if k <= one_count:
    print(1)
  else:
    print(s[one_count])
else:
  print(s[0])


### FIXED CODE ###

s = input()
k = int(input())

if int(s[0]) == 1:
  one_count = 0
  i = 0
  while i < len(s) and int(s[i]) == 1:
    one_count += 1
    i += 1
  if k <= one_count:
    print(1)
  else:
    print(s[one_count])
else:
  print(s[0])
import math
N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
for i in range(N):
	v = (v * (N-i)//(i+1))
	ncr[i+1] = v%mod																															


g = math.gcd(A,B)
if K % g != 0:
	print(0)
	exit(0)

A //= g
B //= g
K //= g
pat = 0
for a in range(N):
	if (K - (a * A)) % B == 0:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)
	



### FIXED CODE ###

N,A,B,K = map(int,input().split(" "))
mod = 998244353
ncr = [1]*(N+1)
v = 1
for i in range(N):
	v = (v * ((N-i)%mod) * pow((i+1),mod-2,mod)) % mod
	ncr[i+1] = v%mod

pat = 0
for a in range(N+1):
	if (K - (a * A) < 0):
		break
	if (K - (a * A)) % B == 0 and ((K - (a * A))//B) <= N:
		pat += ncr[a]*ncr[(K - (a * A))//B]
		pat %= mod

print(pat % mod)
import math
targ = int(input())
y,z = 0,0
while True:
    minans = float("inf")
    for n in range(math.ceil(targ ** ( 1 / 3))+1):
        if minans == 0:
            break
        m = int(math.sqrt(targ - n**3))
        if (n ** 3) + (m **2) > targ:
            break
        if minans > targ - (n ** 3 + m**2) + n + m:
            minans = targ - (n ** 3 + m**2) + n + m
    if minans != float("inf"):
        print(minans)
    else:
        print(y + z)
    targ = int(input())
    if targ == 0:
        break
            

### FIXED CODE ###

import math
targ = int(input())
y,z = 0,0
while True:
    minans = float("inf")
    for n in range(math.ceil(targ ** ( 1 / 3))+1):
        if minans == 0:
            break
        if targ - n**3 >= 0:
            m = int((targ - n**3) **(1/2))
        else:
            m = 0
        if (n ** 3) + (m **2) > targ:
            break
        if minans > targ - (n ** 3 + m**2) + n + m:
            minans = targ - (n ** 3 + m**2) + n + m
    if minans != float("inf"):
        print(minans)
    else:
        print(y + z)
    targ = int(input())
    if targ == 0:
        break
n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pa, pb = [0] * (n+1), [0] * (m+1)
for i in range(n):
    pa[i+1] = pa[i] + a[i]
for i in range(m):
    pb[i+1] = pb[i] + b[i]
mx = 0
for i in range(len(pa)):
    j = m
    if pa[i] > k:
        break
    v = k - pa[i]
    while pb[j] <= v:
        j -= 1
    mx = max(mx, i+j)
print(mx)


### FIXED CODE ###

n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pa, pb = [0] * (n+1), [0] * (m+1)
for i in range(n):
    pa[i+1] = pa[i] + a[i]
for i in range(m):
    pb[i+1] = pb[i] + b[i]
mx = 0
j = m
for i in range(n+1):
    if pa[i] > k:
        break
    v = k - pa[i]
    while pb[j] > v:
        j -= 1
    mx = max(mx, i+j)
print(mx)
# -*- coding: utf-8 -*-

import numpy as np

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

def main():

    n, m, x= map(int, input().split())
    matrix = []
    for t in range(n):
        matrix.append(list(map(int,input().split())))

    l= []

    for i in range(n):
        for pair in combinations(matrix, i+1):
            row_sum = np.sum(pair, axis=0)
            for j in range(len(row_sum)):
                if j == 0:
                    continue
                if row_sum[j] < x:
                    break
                l.append(row_sum[0])
    if len(l) == 0:
        print('-1')
    else:
        print(min(l))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

import itertools
import numpy as np


def main():

    n, m, x= map(int, input().split())
    matrix = np.array([list(map(int, input().split())) for _ in range(n)], dtype=np.int32)

    out = 10**18
    for i in itertools.product([False,True], repeat=n):
        row_sum = np.sum(matrix[np.where(i)], axis=0)
        if m == np.count_nonzero(row_sum[1:] >= x):
            out = min(out, row_sum[0])

    if out == 10**18:
        print('-1')
    else:
        print(out)


if __name__ == '__main__':
    main()
a,v =  map(int, input().split())
b,w =  map(int, input().split())
t = int(input())

if abs(w*t+b)-abs(v*t+a) >=0:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

s = input()
print(s[:3])
N = input()
a = list(map(int,input().split()))
b = 0

for i in range(N):
  if a[i] % 2 == 0:
    if a[i] % 3 != 0:
      if a[i] % 5 != 0:
     	b = 1
      	break
if b == 0:
  print("APPROVED")
else:
  print("DENIED")


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
c = 0
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] %3 != 0 :
            if A[i] %5 != 0:
                c = 1
                break
if c == 0:
    print("APPROVED")
else:
    print("DENIED")
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

alpha = "abcdefghijklmnopqrstuvwxyz"

s = raw_input()
K = int(raw_input())
dic = dict([alpha[i], i] for i in xrange(len(alpha)))

ans = [] 
for si in s:
    d = 26 - dic[si] if si != "a" else 0
    if d <= K:
        ans.append("a")
        K -= d
    else:
        ans.append(si)

if K > 0:
    ans[-1] = alpha[dic[ans[-1]] + K]

print "".join(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

alpha = "abcdefghijklmnopqrstuvwxyz"

s = raw_input()
K = int(raw_input())
dic = dict([alpha[i], i] for i in xrange(len(alpha)))

ans = [] 
for si in s:
    d = 26 - dic[si] if si != "a" else 0
    if d <= K:
        ans.append("a")
        K -= d
    else:
        ans.append(si)

if K > 0:
    ans[-1] = alpha[(dic[ans[-1]] + K) % 26]

print "".join(ans)
N,A = map(int,input().split())
X = list(map(int,input().split()))

MAXSUM = sum(X)+5
dp = [[[0 for _ in range(MAXSUM)] for _ in range(N+5)] for _ in range(N+5)]
for i in range(N):
  dp[i+1][1][X[i]] += 1
  for k in range(N):
    for j in range(MAXSUM):
      dp[i+1][k][j] += dp[i][k][j]
      if X[i]+j < MAXSUM:
        dp[i+1][k+1][X[i]+j] += dp[i][k][j]
#print(dp)
ans = 0
for i in range(N):
  ans += dp[N][i+1][A*(i+1)]
print(ans)

### FIXED CODE ###

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

MAXSUM = sum(X)+5
dp = [[[0 for _ in range(MAXSUM)] for _ in range(N+5)] for _ in range(N+5)]
for i in range(N):
  dp[i+1][1][X[i]] += 1
  for k in range(N):
    for j in range(MAXSUM):
      dp[i+1][k][j] += dp[i][k][j]
      if X[i]+j < MAXSUM:
        dp[i+1][k+1][X[i]+j] += dp[i][k][j]
#print(dp)
ans = 0
for i in range(N):
  if A*(i+1) < MAXSUM:
    ans += dp[N][i+1][A*(i+1)]
print(ans)
A,B =map(int,input().split())
 
# 元の価格ｘ,8%  y、１０％
x = A/0.08
x_1 =(A+1)/0.08
y = B/0.1
y_1 = (B+1)/0.1

x_2 = {i for i in range(int(x),int(x_1) +1) }
y_2 = {i for i in range(int(y),int(y_1) +1) }
moto_nedan = x_2 & y_2
if len(moto_nedan) == 0:
    print("-1")
else:
    print(min(moto_nedan))
print(x_2)
print(y_2)
print(38*0.08)


### FIXED CODE ###

# 初期入力
S = input()

# 3つとも同じ会社だったらバスはない
s_list =[i for i in S]
if s_list[0] == s_list[1] and s_list[1] ==s_list[2]:
    print("No")
else:
    print("Yes")
arr = list(map(int, input().split()))


i=1
for num in arr:
    if(num==0):
        print(i)
    else:
        i++;


### FIXED CODE ###

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


i=1
for num in arr:
    if(num==0):
        print(i)
    else:
        i = i +1
N = int(input())
A = list(map(int,input().split()))
A.sort()
res = 0
Ab = [True] * N
cnt = 0
for i in range(N):
    if not Ab[i]:
        continue
    for j in range(i+1,N):
        if Ab[j] :
            if A[j] % A[i] == 0:
                 Ab[j] = False
                if A[i] == A[j]:
                    Ab[i] = False
print(Ab.count(True))



### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)
n = int(input())
a = list(map(int, input().split()))
c = []

for i in b:
    c.append(a.index(i)+1)

print(' '.join(map(str, c)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
index=[0]*n

for i in range(n):
    index[a[i]-1] = i+1

print(' '.join(map(str, index)))
n = int(input())
s = input()

a = s[n/2:]
b = s[:n/2]

if a==b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys

n = int(input())
s = input()
 
if n%2 == 1:
  print("No")
  sys.exit()
 
slise = (n/2)
a = s[:int(slise)]
b = s[int(slise):]
 
if a==b:
  print("Yes")
else:
  print("No")
a=int(input())

print(long((a - 1) * a / 2))

### FIXED CODE ###

a=int(input())

print(((a - 1) * a // 2))
a=list(input())
b=list(input())
d=""
for i in range(0,len(a)):
    c=a[i]+b[i]
    d=d+c
print(d)

### FIXED CODE ###

a=list(input())
b=list(input())
d=""
for i in range(0,len(b)):
    c=a[i]+b[i]
    d=d+c

if len(b)+1 == len(a):
    d = d+ a[len(a)-1]

print(d)
S = import()
if S == ABC:
  print("ARC")
else:
  print("ABC")

### FIXED CODE ###

S = input()
if S == "ABC":
  print("ARC")
else:
  print("ABC")
H,W = (int(i) for i in input().split())

a = [0 for i in range(H)]

for i in range(H):
    a[i] = list(input())

count = 0
check = []
for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            count = 1
            break
    if count == 0:
        check.append(i)
    count = 0

for i in check:
    del a[i]

ck = []
for i in range(W):
    for j in range(len(a)):
        if a[j][i] == '#':
            count = 1
            break
    if count == 0:
        ck.append(i)
    count = 0

for i in ck:
    for j in range(len(a)):
        del a[j][i]

ans = ''
for i in range(len(a)):
    for j in a[i]:
        ans += j
    print(ans)
    ans = ''

### FIXED CODE ###

H,W = (int(i) for i in input().split())

a = [0 for i in range(H)]

for i in range(H):
    a[i] = list(input())

count = 0
check = []
n = 0
for i in range(H):
    for j in range(W):
        if a[i-n][j] == '#':
            count = 1
            break
    if count == 0:
        del a[i-n]
        n += 1
    count = 0

ck = []
n = 0
for i in range(W):
    for j in range(len(a)):
        if a[j][i] == '#':
            count = 1
            break
    if count == 0:
        ck.append(i)
    count = 0

for i in ck:
    for j in range(len(a)):
        del a[j][i-n]
    n += 1

ans = ''
for i in range(len(a)):
    for j in a[i]:
        ans += j
    print(ans)
    ans = ''
N, K = map(int, input().split())
S = input()
if S[K] == "A":
  S[K] = "a"
elif S[K] == "B":
  S[K] = "b"
else:
  S[K] = "c"
print(S)

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
if S[K-1] == "A":
  S[K-1] = "a"
elif S[K-1] == "B":
  S[K-1] = "b"
else:
  S[K-1] = "c"
ans = "".join(S)
print(ans)
a, b = int(input()), int(input())
print(a * b, 2 * (a + b))



### FIXED CODE ###

a, b = list(map(int, input().split()))
print(a * b, 2 * (a + b))
N,M=map(int,input().split())
mp=[[] for i in range(N+1)]
for i in range(M):
  L,R,D=map(int,input().split())
  mp[L].append([R,D])
  mp[R].append([L,-D])

dist=[None]*(N+1)

def dfs(n):
  for np,nd in mp[n]:
    if dist[np] is None:
      dist[np]=dist[n]+nd
      if not dfs(np):
        return False
    else:
      if dist[np]!=dist[n]+nd:
        return False
  return True
ans=True
for i in range(1,N+1):
  if dist[i] is None:
    dist[i]=0
    if not dfs(i):
      ans=False
      break
if ans:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)

N,M=map(int,input().split())
mp=[[] for i in range(N+1)]
for i in range(M):
  L,R,D=map(int,input().split())
  mp[L].append([R,D])
  mp[R].append([L,-D])

dist=[None]*(N+1)

def dfs(n):
  for np,nd in mp[n]:
    if dist[np] is None:
      dist[np]=dist[n]+nd
      if not dfs(np):
        return False
    else:
      if dist[np]!=dist[n]+nd:
        return False
  return True
ans=True
for i in range(1,N+1):
  if dist[i] is None:
    dist[i]=0
    if not dfs(i):
      ans=False
      break
if ans:
  print("Yes")
else:
  print("No")
from operator import mul
from functools import reduce

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(1,k+1):
    print( ((cmb(k-1, i-1) %mod) * (cmb(n-k+1,i) %mod) ) %mod )

### FIXED CODE ###

from math import factorial as f
n,k=map(int,input().split())
mod=10**9+7
for i in range(1,k+1):
    if i>n-k+1:
        print(0)
    else:
        a= f(k-1)  // (f(i-1) * f(k-i))  %mod
        b= f(n-k+1)// (f(i) * f(n-k-i+1))%mod
        print( a*b %mod )
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import math
def sub(a,b,c,d):
    x1 = a - (a - (c+1))//b * b
    if d<b:
        ans = "No"
    elif a<b:
        ans = "No"
    elif d%b==0:
        if x1>=b:
            ans = "Yes"
        else:
            ans = "No"
    else:
        k = math.gcd(d,b)
        x2 = x1 - (x1 - (c+1))//k * k
        if x2>=b:
            ans = "Yes"
        else:
            ans = "No"
    return ans

t = int(input())
ans = []
for i in range(t):
    a,b,c,d = map(int, input().split())
    ans.append(sub(a,b,c,d))
write("\n".join(ans))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def sub(a,b,c,d):
    x1 = a - (a - (c+1))//b * b
    if d<b:
        ans = "No"
    elif a<b:
        ans = "No"
    elif d%b==0:
        if x1>=b:
            ans = "Yes"
        else:
            ans = "No"
    else:
        k = gcd(d,b)
        x2 = x1 - (x1 - (c+1))//k * k
        if x2>=b:
            ans = "Yes"
        else:
            ans = "No"
    return ans

t = int(input())
ans = []
for i in range(t):
    a,b,c,d = map(int, input().split())
    ans.append(sub(a,b,c,d))
write("\n".join(ans))
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
input = sys.stdin.readline
a,b,x= map(float,input().split())
if x > a*a*b/2:
    left = (x-a*a*b/2)/a
    tei = left*2/a
    left1 = b-tei
    ans = math.atan(a/left1)
    print(90-math.degrees(ans))
else:
    left = x/a
    tei = left*2/b
    ans = math.atan(b/tei)
    print(math.degrees(ans))


### FIXED 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
input = sys.stdin.readline
a,b,x= map(float,input().split())
if x == a*a*b:
    print(0)
else:
    if x > a*a*b/2:
        left = (x-a*a*b/2)/a
        tei = left*2/a
        left1 = b-tei
        ans = math.atan(a/left1)
        print(90-math.degrees(ans))
    else:
        left = x/a
        tei = left*2/b
        ans = math.atan(b/tei)
        print(math.degrees(ans))
x = int(input())
if x>=30:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

x = int(input())
if x>=30:
  print('Yes')
else:
  print('No')
s = input()

# x を除いたときに回文になっていなければ達成不可能
if s.replace('x', '') != s.replace('x', '')[::-1]:
    print(-1)
    exit()

ans = 0

l = 0
r = len(s)-1

while l != r:
    if s[l] == s[r]:
        l += 1
        r -= 1
    elif s[l] == 'x':
        ans += 1
        l += 1
    elif s[r] == 'x':
        ans += 1
        r -= 1
    else:
        print('error')
        exit()
print(ans)


### FIXED CODE ###

s = input()

# x を除いたときに回文になっていなければ達成不可能
if s.replace('x', '') != s.replace('x', '')[::-1]:
    print(-1)
    exit()

ans = 0

l = 0
r = len(s)-1

while l < r:
    if s[l] == s[r]:
        l += 1
        r -= 1
    elif s[l] == 'x':
        ans += 1
        l += 1
    elif s[r] == 'x':
        ans += 1
        r -= 1
    else:
        print('error')
        exit()
print(ans)
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  dp=[[inf]*(50*50)for _ in range(n)]
  kakutei=[[0]*(50*50)for _ in range(n)]
  dp[0][min(s,50*50-1)]=0
  todo=[[0,0,min(s,50*50-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
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)


### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
import math
ans = 0
mod = 10**9+7
a = 0
ans = 0
for i in range(N-1):
  a += pow(i+1,mod-2,mod)
  ans += ((X[i+1]-X[i])%mod)*(a%mod)
  ans %= mod
  
ans *= math.factorial(N-1)%mod

print(ans%mod)