Harryxun/stf_run huggingface dataset:
from bisect import bisect as list_bisect
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M,V,P = map(int,input().split())
A = sorted(map(int,input().split()))
def judge(i):
    if len(A) <= P:
        return True
    a = A[i]
    if V <= P:
        return a+M >= A[-P]
    k = max2(0,V-P+1-i)
    if k-P >= 0:
        return False
    else:
        return a+M > A[-P+k]

i = bisect(-1,N-1,judge)
x = A[i]
while A[i-1] == x:
    i -= 1
print(N-i)


### FIXED CODE ###

from bisect import bisect as list_bisect
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M,V,P = map(int,input().split())
A = sorted(map(int,input().split()))

k = N-P
def judge(i):
    if i >= k:
        return True
    a = A[i]
    if a+M < A[k]:
        return False

    r = 0
    for v in A[i+1:k+1]:
        r += a+M-v
    return r >= (V-P-i)*M

i = bisect(-1,N-1,judge)
print(N-i)
a=input()
b=input()

if a > b:
    printf("GREATER")
elif a < b:
    print("LESS")
else:
    print("EQUAL")

### FIXED CODE ###

a=int(input())
b=int(input())

if a > b:
    print("GREATER")
elif a < b:
    print("LESS")
else:
    print("EQUAL")
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [0]*N
count = 0

for n in range(N):
  A[n] = list(map(int, input().split()))
  
  for i in range(M):
    _sum += A[n][i] * B[i]
    
  if _sum + C > 0:
    count += 1
  else:
    continue
    
print(count)

### FIXED CODE ###

N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [0]*N
count = 0

def a_x_b(ab):
  a, b = ab
  return a*b

for n in range(N):
  A[n] = list(map(int, input().split()))
  AB = [(A[n][i], B[i]) for i in range(M)]
  if sum(list(map(a_x_b, AB)))+C > 0:
    count += 1
  else:
    continue
    
print(count)
import math
r = input()
m = (r ** 2) * math.pi
l = r * 2 * math.pi
print('{} {}'.format(m, l))

### FIXED CODE ###

import math
r = float(input())
m = r ** 2 * math.pi
l = r * 2 * math.pi
print('{:.6f} {:.6f}'.format(m, l))
N=int(input())
    s = [''.join(sorted(input())) for _ in range(N)]
    from collections import Counter
    c = Counter(s)
    print(sum((x*(x-1))//2 for x in c.values()))

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]
from collections import Counter

c = Counter(s)
print(sum((x * (x - 1)) // 2 for x in c.values()))
R,C,K=map(int,input().split())
r,m=range,max
G=[[0]*(C+1)for i in r(R+1)]
for i in'_'*K:r,c,v=map(int,input().split());G[r][c]=v
F=[[[0]*(C+1)for i in r(R+1)]for i in r(4)]
for r in r(1,R+1):
	for x in r(1,4):
		for c in r(1,C+1):F[x][r][c]=m(F[x-1][r][c-1]+G[r][c],F[x][r][c-1],(x<2)*(G[r][c]+m(F[1][r-1][c],F[2][r-1][c],F[3][r-1][c])))
print(m(F[1][R][C],F[2][R][C],F[3][R][C]))

### FIXED CODE ###

R,C,K=map(int,input().split())
f,g=range,max
G=[[0]*(C+1)for i in f(R+1)]
for i in'_'*K:r,c,v=map(int,input().split());G[r][c]=v
F=[[[0]*(C+1)for i in f(R+1)]for i in f(4)]
for r in f(1,R+1):
	for x in f(1,4):
		for c in f(1,C+1):F[x][r][c]=g(F[x-1][r][c-1]+G[r][c],F[x][r][c-1],(x<2)*(G[r][c]+g(F[1][r-1][c],F[2][r-1][c],F[3][r-1][c])))
print(g(F[1][R][C],F[2][R][C],F[3][R][C]))
A, B = map(int, input().split())
if A == B:
  print("EQUAL")
if A > B:
  print("GREATER")
if A < B:
  print("LESS")

### FIXED CODE ###

A = int(input())
B = int(input())
if A == B:
  print("EQUAL")
if A > B:
  print("GREATER")
if A < B:
  print("LESS")
import sys
# sys.stdin = open('input.txt')

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(len(a)):
    a[i] -= 1

cycle = n + 1
sub = []
place = 0

for i in range(len(a)):
    place = a[i]
    sub.append(a[i])
    if place == 0:
        sub = sub[:-1]
        cycle = i
        break

# print(cycle, sub)
ans = sub[k%cycle] + 1
print(ans)

### FIXED CODE ###

import sys
# sys.stdin = open('input.txt')

n, k = map(int, input().split())
a = list(map(int, input().split()))

s = []  #　頂点を訪れた順番に持つ数列
ord = [-1 for i in range(n+1)]  # 訪問済みの頂点の index. 未訪問のときは -1
c = 1  # 周期
l = 0  # 例外部分の長さ

v = 1  # 現在の頂点
while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v-1]

l = ord[v]
c = len(s) - l

if k < l:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])
def main():
    X = input()
    A = [100,101,102,103,104,105]
    last = int(X[:len(X)-2])
    two = int(X[-2:])
    if two <= last*5:
        print(1)
    else:
        print(0)

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    X = input()
    if(len(X)<3):
        print(0)
        return
    last = int(X[:len(X)-2])
    two = int(X[-2:])
    if two <= last*5:
        print(1)
    else:
        print(0)

if __name__=='__main__':
    main()
import numpy as np
import math

def lcm(x, y):
	return (x * y) // math.gcd(x, y)

a = input()
a, b, c, d = [int(i) for i in a.split(" ")]
dc = (b // c) - ((a-1) // c)
dd = (b // d) - ((a-1)  // d)
dcd = (b // lcm(c, d)) - ((a-1) // lcm(c, d))
print((b - a) + 1 - (dc + dd - dcd))

### FIXED CODE ###

import fractions

def lcm(x, y):
	return (x * y) // fractions.gcd(x, y)

a = input()
a, b, c, d = [int(i) for i in a.split(" ")]
dc = (b // c) - ((a-1) // c)
dd = (b // d) - ((a-1)  // d)
dcd = (b // lcm(c, d)) - ((a-1) // lcm(c, d))
print((b - a) + 1 - (dc + dd - dcd))
a,b=(int,input().split())
if a<10 and b<10:
  print(a*b)
  
else:
  print('-1')


### FIXED CODE ###

a,b=map(int,input().split())
if a<10 and b<10:
  print(a*b)
  
else:
  print('-1')
from sys import stdin, setrecursionlimit


def dfs(f, v, seen):
    seen[v] = True

    for nv in f[v]:
        if seen[nv]:
            continue
        dfs(f, nv, seen)


def main():
    n, m, k = map(int, stdin.readline().split())

    f = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f[a - 1].append(b - 1)
        f[b - 1].append(a - 1)

    b = [[] for _ in range(n)]

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        b[c - 1].append(d - 1)
        b[d - 1].append(c - 1)

    ans = [0] * n
    for i in range(n):
        seen = [False] * n
        dfs(f, i, seen)
        arr = []
        for j in range(n):
            if seen[j]:
                arr.append(j)
        tmp = len(set(arr) - set(f[i]) - set(b[i]))
        tmp -= 1
        ans[i] = tmp

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0:
            x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        p = self.parent
        if x != y:
            x, y = sorted([x, y])
            p[x], p[y] = p[x] + p[y], x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parent[self.find(x)]


def main():
    n, m, k = map(int, stdin.readline().split())

    f = UnionFindTree(n)

    f_or_b = [0] * n

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f.union(a - 1, b - 1)
        f_or_b[a - 1] += 1
        f_or_b[b - 1] += 1

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        if f.same(c - 1, d - 1):
            f_or_b[c - 1] += 1
            f_or_b[d - 1] += 1

    print(*[f.size(i) - f_or_b[i] - 1 for i in range(n)])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()
n, k = map(int, input().split())
prices = list(map(input().split()))
print(sum(sorted(prices[:k])))

### FIXED CODE ###

n, k = map(int, input().split())
price = list(map(int, input().split()))
print(sum(sorted(price)[:k]))
import math

a, b, x = map(int, input().split())

if x > (a ** 2) * b / 2:
	arg = (2 * b / a) - (2 * x / (a ** 3))
elif x == (a ** 2) * b / 2:
	arg = atan2(b, a)
else:
	arg = (a * (b ** 2)) / (2 * x)

print(math.atan(arg) / math.pi * 180)

### FIXED CODE ###

import math

a, b, x = map(int, input().split())

if x > (a ** 2) * b / 2:
	arg = (2 * b / a) - (2 * x / (a ** 3))
else:
	arg = (a * (b ** 2)) / (2 * x)

print(math.atan(arg) / math.pi * 180)
import sympy as sp

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

a = sorted(a)
ads = [0]*(2*10**5)

ans = 0
dups = []
for ai in a:
    ds = sp.divisors(ai)
    ok = True
    if ads[ai]:
        if ai not in dups:
            dups.append(ai)
        continue
    for d in ds:
        if ads[d]:
            ok = False
            break
    if ok:
        ads[ai] = 1
        ans += 1

print(ans - len(dups))

### FIXED CODE ###

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

a = sorted(a)

dp  = [0] * (a[-1]+1)

for ai in a:
    if dp[ai]:
        dp[ai] += 1
        continue

    i = 1
    while True:
        if ai*i >= len(dp):
            break
        dp[ai*i] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai] == 1:
        ans += 1

print(ans)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys

f = open("/Users/naoki/Documents/Atcoder/input.txt")

N, M = map(int, f.readline().split())
uvs = [list(map(lambda x:int(x)-1, f.readline().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, f.readline().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.pop()
    next_targets = deque([checking])
    for i in range(3):
        purposes = []
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.append(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] == -10000:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()
import sys
import numpy as np
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)] + [None]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    colors = defaultdict(list)
    for i, c in enumerate(C):
        colors[c].append(i)

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        # i個目を塗らない
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
        for j in colors[C[i]]:
            if j <= i:
                continue

            # ぬる
            dp[j + 1] += dp[i]
            dp[j + 1] %= MOD

    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)] + [-1]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * N
    dp[0] = 1
    used = [-1] * (max(C) + 1)
    used[C[0]] = 0

    for i in range(1, N):
        if used[C[i]] == -1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[used[C[i]]]

        dp[i] %= MOD
        used[C[i]] = i

    print(dp[-1])


if __name__ == "__main__":
    main()
A,B=map(int,input().split())
if A>B:
  print(">")
elif A<B:
  print("<")
else:
  print("=")


### FIXED CODE ###

S=input()
A=ord(S[0])
B=ord(S[2])

if A>B:
  print(">")
elif A<B:
  print("<")
else:
  print("=")
n = int(input())
a_list = list(map(int, input().split()))
def count_2(num):
    count = 0
    while num%2 == 0:
        num /= 2
        pritn(num)
        count += 1
    return count
ans = 0
for i in range(n):
    ans += count_2(a_list[i])
print(ans)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
def count_2(num):
    count = 0
    while num%2 == 0:
        num /= 2
        count += 1
    return count
ans = 0
for i in range(n):
    ans += count_2(a_list[i])
print(ans)
#include <iostream>
using namespace std;
int main() {
  int N, M;
  cin >> N >> M;
  char A[50][50], B[50][50];
  for(int i=0; i<N; ++i) scanf("%s", &A[i][0]);
  for(int i=0; i<M; ++i) scanf("%s", &B[i][0]);
  for(int Ay=0; Ay<=N-M; ++Ay)for(int Ax=0; Ax<=N-M; ++Ax)
      if([&](int x, int y){
        for(int i = 0, j = 0; i < M; i+= j >= M ? j=0,1 :j++,0)
          if(A[x+i][y+j] != B[i][j]) return 0;
        return 1;
      }(Ax, Ay))
      {
        cout << "Yes" << endl;
        return 0;
      }
  cout << "No" << endl;
  return 0;
}


### FIXED CODE ###

N, M = map(int, input().split())

f = lambda x: 1 if x == "#" else 0
A = [list(map(f, input())) for _ in range(N)]
B = [list(map(f, input())) for _ in range(M)]

def func():
  for i in range(N-M+1):
    for j in range(N-M+1):
      if all(A[i+k][j+l] == B[k][l] for k in range(M) for l in range(M)):
        return True
  return False

print("Yes" if func() else "No")
def factorial(n):
    if n == 0:
        return 1.0
    else:
        return n*factorial(n-1)


n = int(raw_input())
k = n
arr = []
while(k > 0):
    x, y = map(int, raw_input().split())
    arr.append((x, y))
    k -= 1

total = 0.0
for i in range(n):
    x1 = arr[i][0]
    x2 = arr[i][1]
    for j in range(i+1, n, 1):
        y1 = arr[j][0]
        y2 = arr[j][1]
        dist = (x1-y1)*(x1-y1) + (x2-y2)*(x2-y2)
        print dist
        dist = float(math.sqrt(dist))
        dist = dist * float((factorial(n-1)*2))
        total += dist * float(1/factorial(n))

print total

### FIXED CODE ###

import math
 
def factorial(n):
    if n == 0:
        return 1.0
    else:
        return n*factorial(n-1)
 
 
n = int(raw_input())
k = n
arr = []
while(k > 0):
    x, y = map(int, raw_input().split())
    arr.append((x, y))
    k -= 1
 
total = 0.0
for i in range(n):
    x1 = arr[i][0]
    x2 = arr[i][1]
    for j in range(i+1, n, 1):
        y1 = arr[j][0]
        y2 = arr[j][1]
        dist = (x1-y1)*(x1-y1) + (x2-y2)*(x2-y2)
        dist = float(math.sqrt(dist))
        dist = dist * float((factorial(n-1)*2))
        total += dist * float(1/factorial(n))
 
print total
N,K = map(int,input().split())
S = input()+'2'
L = []
if S[0] == '0':
    L.append(1)
for i in range(1,N):
    if S[i] != S[i+1]:
        L.append(i+1)
for i in range(0,len(L)-K*2,2):
    ans = L[i+K*2]-(L[i]-1)#L[i-1]?
ans = 1 if N == 1 else ans
ans = 3 if N == 3 else ans
ans = 2 if N == 2 or S == '010' else ans
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
S = input()
L = [0]
ans = 0
res = '1'
i = 0
for s in S:
    if s != res:
        L.append(i)
        i += 1
    else:
        i += 1
    res = s
L.append(i)
L.append(i)
if len(L)<=2*K+1:
    ans = N
for i in range(0,len(L)-K*2-1,2):
    ans = max(ans,L[i+K*2+1]-L[i])
print(ans)
n=input()
print(sum([int(j) for j in input().split()])-n)

### FIXED CODE ###

n=int(input())
print(sum([int(j) for j in input().split()])-n)
s = input()
t = input()
s.sort()
t.sort()
if s < t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = str(input())
T = str(input())
S=sorted(S)
T=sorted(T, reverse=True)
if S < T:
    print("Yes")
else:
    print("No")
from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(list)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
    
   
def dfs(node):
    
    s = set()
    stack = deque([node])
    while stack:
        
        n = stack.popleft()
        s.add(n)
        for i in d[n]:
            if i not in s and visited[i] == 0:
                stack.append(i)
                
    return s
    

keys = list(d.keys())
m = max(keys)
visited = [0]*(m+1)
ans = 0

for key in keys:
    if visited[key] == 0:
        s = dfs(key)
        ans = max(ans,len(s))
        for i in s:
            visited[i] = 1


print(ans)
        

### FIXED CODE ###

from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(set)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
    
visited = set()

def dfs(node):
    
    c = 0
    stack = deque([node])
    visited.add(node)
    while stack:
        n = stack.popleft()
        c+=1
        for i in d[n]:
            if  i not in visited:
                visited.add(i)
                stack.append(i)
                
    return c
    

ans = 1

for key in list(d.keys()):
    if key not in visited:

        c = dfs(key)
        ans = max(ans, c)
        


print(ans)
N, Y = map(int, input().split())
ans = 0
a = 0
b = 0
c = 0
for a in range(N+1):
    for b in range(N-a+1):
        c = N - a - b
        if (a*10000 + b*5000 + c*1000) == Y:
            ans = 1
            x = a
            y = b
            z = c
            flag = True #フラグ変数で代用しても良い
            break
    if flag:
        break
if ans == 1:
    print(x,y,z)
else:
    print( '-1 -1 -1')

### FIXED CODE ###

N,Y=map(int,input().split())
answer=-1,-1,-1
for x in range(N+1):
    for y in range(N-x+1):
        z=N-x-y
        if 0<=z<=2000 and 10000*x+5000*y+1000*z==Y:
            answer=x,y,z
            break
    else:
        continue
    break
print(*answer)
m, n = map(int,input().split())
l = map(str,input().split())
l2 = {str(i) for i in range(10)}
l3 = set(l2) - set(l)

ans = 0
for i in range(m, 100000):
    nums = set(str(i))
    if nums <= l3:
        print(i)
        break

### FIXED CODE ###

a = list(map(int,input().split()))
if a.count(5) == 2 and a.count(7) == 1:
  print("YES")
else:
  print("NO")
s = input()
t = input()

ans = []
for i in range(len(s)-(len(t)-1)):
    f = True
    for j in range(len(t)):
        if s[-(j+i+1)] != t[-(j+1)] and s[-(j+i+1)] != '?':
            f = False
    if f == True:
        s = s[:-(len(t)+i)] + t + s[len(s)-1-i:0]
        s = s.replace('?','a')
        ans.append(s)



if len(ans) > 0:
    print(sorted(ans)[0])
else:
    print('UNRESTORABLE')

### FIXED CODE ###

s = input()
t = input()

ans = []
for i in range(len(s)-(len(t)-1)):
    f = True
    for j in range(len(t)):
        if s[j+i] != t[j] and s[j+i] != '?':
            f = False
    if f == True:
        s2 = s[:i] + t + s[i+len(t):]
        s2 = s2.replace('?','a')
        ans.append(s2)



if len(ans) > 0:
    print(min(ans))
else:
    print('UNRESTORABLE')
A=map(int,input())
B=map(int,input())
C=6-A-B
print(C)

### FIXED CODE ###

A=int(input())
B=int(input())  
C=6-A-B
print(C)
n ,m = map(int, input().split())
result = set()
first = True
for i in range(m):
    l, r = map(int, input().split())
    tmp = set()
    for i in range(l, r + 1):
        tmp.add(i)
    if first:
        result = tmp
        # print("tmp {}".format(tmp))
        first = False
    else:
        result = result.intersection(tmp)
        # print("result {} tmp {}".format(result, tmp))

print(len(result))

### FIXED CODE ###

a, b = map(int, input().split())

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




if __name__ == '__main__':
    main()

### FIXED CODE ###

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

        for k in range(N-1):
            r += (slimes[-1]-slimes[-2-k]) * f * pow((N-k-1),MOD-2,MOD)
            r %= MOD
        return r
    print(calc(0,X))




if __name__ == '__main__':
    main()
a,b,c = map(input().split())
out = a[0] + b[0] + c[0]
print(out)

### FIXED CODE ###

a,b,c = map(str, input().split())
out = a[0] + b[0] + c[0]
print(out)
n, m = map(int, input().split())
Ton = [False]*n
Fr1 = [False]*n
for i in range(m):
    a, b = map(int, input().split())
    if b==n:
        Ton[a] = True
    if a==1:
        Fr1[b] = True

r = 'IMPOSSIBLE'
for i in range(m):
    if Ton[i]==Fr1[i]==True:
        r = 'POSSIBLE'
print(r)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    Ton, Fr1 = set(), set()
    for _ in range(m):
        a, b = map(int, input().split())
        if b==n:
            Ton.add(a)
        if a==1:
            Fr1.add(b)

    print('POSSIBLE' if Ton&Fr1 else 'IMPOSSIBLE')

main()