Harryxun/stf_run huggingface dataset:
from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            #     candidate.add(friend)
            #     count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

### FIXED CODE ###

from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[[None,None] for i in range(N+1)]
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    cnt[0]+=1
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    cnt=[0]
    color =set()
    if counter[i][0] is None:
        friend_tansaku(i,i)
        cnt=cnt[0]
        for aa in color:
            counter[aa]=[color,cnt]
    color,cnt =counter[i][0],counter[i][1]
    for k in block_list[i]:
        if k not in color:
            cnt+=1

    count=cnt-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")
n=int(input())
arr=[]
arr=[int(i) for i in input().split(" ")]
arr=[0]+arr

def dp(x):
    if (x==n):
        return 0
    if(x==n-1):
        return (abs(arr[n]-arr[x]))
    return (min(  dp(x+1)+abs(arr[x]-arr[x+1]), dp(x+2)+abs(arr[x]-arr[x+2]) ))

print(dp(1))




### FIXED CODE ###

n=int(input())
arr=[]
arr=[0]+[int(i) for i in input().split(" ")]
dp=[0]*(n+1)
dp[n]=0
dp[n-1]=abs(arr[n-1]-arr[n])
for i in range(n-2,0,-1):
    dp[i]=min( dp[i+1]+abs(arr[i]-arr[i+1]) , dp[i+2]+abs(arr[i]-arr[i+2]) )
print(dp[1])
n,m=map(int,input().split())
a=[[int(x) for x in input().split()] for _ in range(n)]
d={i:0 for i in range(m)}
for i in range(n):
    k=a[i][0]
    for j in range(k):
        d[a[i][j]] += 1
cnt=0
for key in d:
    if d[key] == n:
        cnt+=1
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
a=[[int(x) for x in input().split()] for _ in range(n)]
d={i:0 for i in range(m)}
for i in range(n):
    k=a[i][0]
    for j in range(k):
        d[a[i][j+1]-1] += 1
cnt=0
for key in d:
    if d[key] == n:
        cnt+=1
print(cnt)
bounds = [sum([26 ** i for i in range(n)]) for n in range(1, 11)]
N = int(input())
for b in reversed(bounds):
    if b <= N:
        break
N -= b 
length = bounds.index(b) + 1
s = ''
for i in range(length - 1, 0, -1):
    idx, N = divmod(N, 26**i)
    s = s + lis[idx]
print(s + lis[N])

### FIXED CODE ###

bounds = [sum([26 ** i for i in range(n)]) for n in range(1, 12)]
lis = 'abcdefghijklmnopqrstuvwxyz'
N = int(input())
for b in reversed(bounds):
    if b <= N:
        break
N -= b 
length = bounds.index(b) + 1
s = ''
for i in range(length - 1, 0, -1):
    idx, N = divmod(N, 26**i)
    s = s + lis[idx]
print(s + lis[N])
s = input()
K = int(input())
result = []
alphabet = list("abcdefghijklmnopqrstuvwxyz")

for u in alphabet:
    for i in range(len(s)):
        if s[i] == u:
            for j in range(len(s) - i):
                result.append(s[i:i + j + 1])
    if len(result) > K:
        break
result = list(set(result))
result.sort()
print(result)
print(result[K - 1])


### FIXED CODE ###

s = input()
K = int(input())
subs = []
for i in range(0, len(s)):
    for j in range(i + 1, K + i + 1 if i + K <= len(s) else len(s) + 1):
        subs.append(s[i:j])


subs = list(set(subs))

subs.sort()
print(subs[K - 1])
N=int(input())
v=map(int,input().split())

v_sorted= sorted(v)
ans = (v_sorted[0]+v_sorted[1])/2

for i in range(3,N+1):
  ans = (ans + v_sorted[i])/2

print (ans)

### FIXED CODE ###

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

v_sorted= sorted(v)
ans = (v_sorted[0]+v_sorted[1])/2

for i in range(2,N):
  ans = (ans + v_sorted[i])/2

print (ans)
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
query = [[0]*N for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1][b-1] = c
    query[b-1][a-1] = c

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in enumerate(lis):
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
query = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])
from scipy.special import comb

N = int(input())
An = [int(x) for x in input().split()]  
Cn = [An.count(i) for i in range(1,N+1)]  # どの数字が何個あるか？

# ボールを全部使えるときの合計を求める
s = 0
for i in range(N):
    if Cn[i] > 1:
        s += int(comb(Cn[i],2))

for k in range(N):
    print(s - (Cn[An[k]-1]-1))

### FIXED CODE ###

import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))
N, M, K = map(int, input().split())
A = list(input().split())
B = list(input().split())

a=0;b=0
cnt=0
while a < len(A) and b < len(B) and K > 0:
  a_ = A[a]
  b_ = B[b]
    
  if a_ > K and b_ > K:
    break
      
  if a_ < b_ and a_ <= K:
    cnt += 1
	K -= a_
    a += 1
  elif a_ >= b_ and b_ <= K:
    cnt += 1
    K -= b_
    b += 1
      
print(cnt)  


### FIXED CODE ###

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

A = [0]
B = [0]
ans = 0

for i in range(n):
    A.append(A[i] + a[i])

for i in range(m):
    B.append(B[i] + b[i])

j = m

for i in range(n + 1):
    if A[i] > k:
        break
    while A[i] + B[j] > k:
        j -= 1
    ans = max(ans, i + j)

print(ans)
import math
n=int(input())
lst=list(map(int,input().split()))
xlst=list(reversed(lst))
#1~5と6のgcdは1~6のgcd
#i番目の左側と右側のgcdを求める
#left[i-1]はlstのi番目までのgcd
#xright[i]はlstのnからi-
#lstのi+1番目は右から見たらn-i+1番目



left=[lst[0]]
xright=[lst[n-1]]
for i in range(1,len(lst)):
    left.append(math.gcd(left[i-1],lst[i]))

for i in reversed(range(0,len(lst)-1)):

    xright.append(math.gcd(xright[n-i-2],lst[i]))


#i-1番目までの左からのgcdはleft[i-2]
#i＋1番目以上のgcdは right[i+2]
result=1
for i in range(n):
    a=math.gcd(left[i-1],xright[i-1])
    if a>result:
        result=a
print(result)

### FIXED CODE ###

a,b,t=map(int,input().split())
print((t//a)*b)
N=int(input())
x0,x1,x2,x3=0,0,0,0
 
for i in range(N)
	Si=input()
  	if Si=='AC':
      x0=x0+1
    
    elif Si=='WA':
      x1=x1+1
    
    elif Si=='TLE':
      x2=x2+1
    
    else Si=='RE':
      x3=x3+1
 
print('AC x' str(x0))
print('WA x' str(x1))
print('TLE x' str(x2))
print('RE x' str(x3))

### FIXED CODE ###

N = int(input())
C0, C1, C2, C3 = 0, 0, 0, 0
for i in range(N):
    Si = input()
    if Si == 'AC':
        C0 += 1
 
    elif Si == 'WA':
        C1  += 1
 
    elif Si == 'TLE':
        C2 += 1
 
    else:
        C3 += 1
 
print('AC x ' + str(C0))
print('WA x ' + str(C1))
print('TLE x ' + str(C2))
print('RE x ' + str(C3))
s = input()
t = input()

def is_restorable(a,b):
    ans = True
    for x,y in zip(a,b):
        if x == y or x == '?':
            pass
        else:
            ans = False
            break
    return ans

s = s[::-1]
t = t[::-1]
s_ = list(s)

can_restore = False
anchor = [0,0]

for i,x in enumerate(s):
    if not can_restore:
        if is_restorable(s[i:i+len(t)],t):
            can_restore = True
            s_[i:i+len(t)] = t
            s_ = s_[::-1]
            s_ = ''.join(s_)

ans = s_.replace('?','a')

print(ans)

### FIXED CODE ###

s = input()
t = input()

def is_restorable(a,b):
    ans = True
    for x,y in zip(a,b):
        if ans:
            if x == y or x == '?':
                pass
            else:
                ans = False
    return ans

s = s[::-1]
t = t[::-1]
s_ = list(s)

can_restore = False

for i,x in enumerate(s):
    if i+len(t) <= len(s):
        if not can_restore:
            if is_restorable(s[i:i+len(t)],t):
                can_restore = True
                s_[i:i+len(t)] = t

s_ = s_[::-1]
s_ = ''.join(s_)

ans = s_.replace('?','a')

if can_restore:
    print(ans)
else:
    print('UNRESTORABLE')
import math
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in ragne(m):
  c=math.floor(max(a)/2)
  a.remove(a[-1])
  a.append(c)
  a.sort()
 
sum=0
for i in range(n):
  sum+=a[i]
  
print(sum)
  

### FIXED CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = [-1*int(i) for i in input().split()]
heapify(A)

for i in range(M):
    n = -1 * heappop(A)
    heappush(A, -1*(n//2))

print(-1*sum(A))
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
if len(np.unique(a)) == 1:
    print(len(a))
else:
    for i in a[::-1][1:]:
        if max(c) <= i:
            c.append(i)
        else:
            mask = np.array(c) - i > 0
            c[mask][np.argmin(c[mask])] = i
    print(len(c))

### FIXED CODE ###

def se(c, x, h, l):
    if h == l:
        return l
    t = (h+l)//2
    if c[t] <= x:
        a = se(c,x,h,t+1)
    else:
        a = se(c,x,t,l)
    return a
        
    
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
diff = np.diff(a)
tmp = np.sum(diff<=0)
if tmp == len(diff):
    print(len(a))
elif tmp == 0:
    print(1)
else:
    for i in a[::-1][1:]:
        if c[-1] <= i:
            c.append(i)
        else:
            c[se(c,i,len(c),0)] = i
    print(len(c))
s = input()
ans = 0
for j in range(len(s)):
  for i in range(j):
    if int(s[i:j+1])%2019 == 0:
      ans+=1
print(ans)

### FIXED CODE ###

s,w = map(int,input().split())
if s<=w:
  print('unsafe')
else:
  print('safe')
A,B,N = map(int, input().split(' '))
c = min(N,B)
if c % B == 0:
    print(int(A(c-1)/B))
else :
    print(int(A(c)/B))

### FIXED CODE ###

A,B,N = map(int, input().split())
c = min(N,B)
if c % B == 0:
    print(int(A*(c-1)/B))
else :
    print(int(A*(c)/B))
N, T = map(int, input().split())
li = [list(map(int, input().split())) for i in range(N)]
li2 = []

if 


for s in li:
  if s[0:] <= T:
    li2 = li2.append(s)
    for t in li2:
      minli = min(li2[:1])
      print(minli)
      
  else:
    print("TLE")

### FIXED CODE ###

n,T = map(int,input().split())
mn = 1001
for i in range(n):
    c,t = map(int,input().split())
    if t <= T:
        mn = min(mn,c)

if mn == 1001:
    print("TLE")
else :
    print(mn)
N, L = map(int, input().split())
print(*sorted(input() for i in range(L)), sep='')

### FIXED CODE ###

N, L = map(int, input().split())
S = [input() for i in range(N)]
s = sorted(S)
print(*s, sep='')
N = input()
str = [input() for i in range(N)]
# print str
a = str[0]
b = str[1]
h = str[2]

S = (a + b) * h // 2
print(S)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
 
print(int((a+b)*h//2))
def main():
    N = input()
    if N%10 != 0:
        print(digitSum(N))
    else:
        print(digitSum(N)*10)

def digitSum(n):
    s = str(n)
    array = list(map(int, list(s)))
    return sum(array)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = input()
    if N%10 != 0:
        print(digitSum(N))
    else:
        print(digitSum(N)*10)

def digitSum(n):
    s = str(n)
    array = list(map(int, list(s)))
    return sum(array)

if __name__ == '__main__':
    main()
import math

d = math.gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    if d % i == 0:
        d //= i
        r += 1
    while d % i == 0:
        d //= i
    i += 1
print(r + (d > 1))


### FIXED CODE ###

from fractions import gcd

d = gcd(*map(int, input().split()))
r = 1
i = 2
while i * i <= d:
    if d % i == 0:
        d //= i
        r += 1
    while d % i == 0:
        d //= i
    i += 1
print(r + (d > 1))
X = int(input())
if X == "A":
  	print("T")
elif X == "T":
  	print("A")
elif X == "C":
  	print("G")
else:
	print("C")

### FIXED CODE ###

X = input()
if X == "A":
  	print("T")
elif X == "T":
  	print("A")
elif X == "C":
  	print("G")
elif X == "G":
	print("C")
A, B, C, X = [int(input()) for i in range(4)]

print(sum(500*a + 100*b + 50*c == X) for a in A for b in B for c in C)

### FIXED CODE ###

A, B, C, X = [int(input()) for _ in range(4)]
print(sum(500*a + 100*b + 50*c == X for a in range(A+1) for b in range(B+1) for c in range(C+1)))
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LI()
    a.sort(
    print(sum[n::2])
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LI()
    a.sort()
    print(sum(a[n::2]))
    return


#main
if __name__ == '__main__':
    solve()
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort()
A.reverse()
B.sort()
B.reverse()
C.sort()
C.reverse()

m = max(X,Y,Z)


ansl = [0] * 3000
tmp = (5,5,5)
inda = 0
indb = 0
indc = 0

hoge = 10**12

sumab = []
for i in range(X):
	for j in range(Y):
		sumab.append(A[i] + B[j])

sumab.sort()
sumab.reverse()

anslist = []
for k in range(K):
	for cc in range(Z):
		anslist.append(sumab[k] + C[cc])
		
anslist.sort()
anslist.reverse()
for aa in range(K):
	print (anslist[aa])

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort()
A.reverse()
B.sort()
B.reverse()
C.sort()
C.reverse()

anslist = []

for i in range(X):
	for j in range(Y):
		for k in range(Z):
			if (i+1)*(j+1)*(k+1) <= K:
				anslist.append(A[i] + B[j] + C[k])
			else:
				break

anslist.sort()
anslist.reverse()
for hoge in range(K):
	print (anslist[hoge])
N=int(input())
A=list(map(int, input().split()))

L=[0]*(10**6)
for i in range(N):
    if i-A[i]>=0:
        L[i-A[i]]+=1
ans=0
for i in range(N):
    tall=A[i]
    ans+=L[tall+i]
print(ans)
#print(L[:10])

### FIXED CODE ###

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

L=[0]*(10**6)
for i in range(N):
    if i-A[i]>=0:
        L[i-A[i]]+=1
ans=0
for i in range(N):
    tall=A[i]
    if tall+i<len(L):
        ans+=L[tall+i]
print(ans)
#print(L[:10])
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    if m==0:
        ans=1
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n:
        ans=1
        if k%2==0:
            for i in a[:k]:
                ans=(ans*i)%MOD
        else:
            for i in a[-k:]:
                ans=(ans*i)%MOD
    else:
        cal=1
        i=(m//2)*2
        for j in a[:i]:
            cal=(cal*j)%MOD
        if k-i>0:
            for j in a[-(k-i):]:
                cal=(cal*j)%MOD
        ans=cal
        for i in range((m//2)*2-2,-2,-2):
            if k-i>n-m:
                break
            for j in a[i-2:i]:
                cal=(cal*pow(j,MOD-2,MOD))%MOD
            if k-i>=0:
                if -(k-i)+2==0:
                    for j in a[-(k-i):]:
                    cal=(cal*j)%MOD
                else:
                    for j in a[-(k-i):-(k-i)+2]:
                        cal=(cal*j)%MOD
            ans=max(ans,cal)
    print(ans)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    ans=1
    if m==0 or (m==n and k%2==1):
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n and k%2==0:
        for i in a[:k]:
            ans=(ans*i)%MOD
    else:
        ans=1
        l,r=0,-1
        lm=a[0]*a[1]
        rm=a[-1]*a[-2]
        for i in range(k//2):
            if lm>=rm:
                ans*=lm%MOD
                l+=2
                if l<=n-2:
                    lm=a[l]*a[l+1]
            else:
                ans*=rm%MOD
                r-=2
                if 1<=n+r:
                    rm=a[r]*a[r-1]
            ans%=MOD
        if k%2==1:
            ans*=a[r]
            ans%=MOD
    print(ans)

if __name__ == '__main__':
    resolve()
import math
n,d=input().split()
n=int(n)
d=int(d)
def combinations(n, r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
x=[]
if d==1:
  count=combinations(n,2)
  count=int(count)
else:
  for i in range(n):
    xa=[int(s) for s in input().split()]
    x.append(xa)
  a=[]
  for i in range(n-1):
    for j in range(i+1,n):
      t=[]
      for k in range(d):
        c=(x[i][k]-x[j][k])*(x[i][k]-x[j][k])
        t.append(c)
        if k==d-1:
          a.append(sum(t))
  answer=list(map(lambda x:pow(x,1/2),a))
  count=0
  for l in range(n):
    if answer[l].is_integer()==True:
      count=count+1
print(count)

### FIXED CODE ###

n=list(map(int,input().split()))
if n[0] * n[1] >= n[2]:
  print(n[2])
else :
  print(n[0] * n[1])
n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())
ans = 0
for i in T:
	if i in n:
		ans += 1
print ans

### FIXED CODE ###

n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())
ans = 0
for i in T:
	if i in S:
		ans += 1
print ans
x,n = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
m = float("inf")
if x<int(p[0]) or int(p[n-1])<x:
  print(x)
else:
  for y in [y for y in range(p[0]-1,p[n-1]) if not y in p]:
    if abs(x-y)<m:
      m = abs(x-y)
      ans_y = y
  print(ans_y)

### FIXED CODE ###

x,n = map(int, input().split())
ans_y = None
if n == 0:
  print(x)
elif n == 1:
  p = list(map(int, input().split()))
  if x == p[0]:
    print(x-1)
  else:
    print(x)
else:
  p = list(map(int, input().split()))
  p.sort()
  m = float("inf")
  if x<p[0] or p[n-1]<x:
    print(x)
  else:
    for y in [y for y in range(p[0]-1,p[n-1]+2) if not y in p]:
      if abs(x-y)<m:
        m = abs(x-y)
        ans_y = y
  if ans_y != None:
    print(ans_y)
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

P = []
M = []
zero = 0
for a in A:
    if a > 0:
        P.append(a)
    elif a < 0:
        M.append(a)
    else:
        zero += 1

# 0 を選ぶしかない場合
if len(P) + len(M) < K:
    print(0)
    exit()

P.sort(reverse=True)
M.sort()

# a >= 0 のとき
if len(P) + zero == N:
    ans = 1
    for k in range(K):
        ans *= P[k]
        ans %= MOD
    print(ans)
    exit()

# a <= 0 のとき
if len(M) + zero == N:
    ans = 1
    if K % 2 == 0:
        for k in range(K):
            ans *= M[k]
            ans %= MOD
        print(ans)
    else:
        if zero > 0:
            print(0)
        else:
            M.sort(reverse=True)
            for k in range(K):
                ans *= M[k]
                ans %= MOD
            print(ans)
    exit()

# a に正・負両方含まれる場合
cur_p = 0
cur_m = 0
ans = 1
for k in range(K):
    if cur_p == len(P):
        ans *= M[cur_m]
        cur_m += 1
    elif cur_m == len(M):
        ans *= P[cur_p]
        cur_p += 1
    else:
        if P[cur_p] < abs(M[cur_m]):
            ans *= M[cur_m]
            cur_m += 1
        else:
            ans *= P[cur_p]
            cur_p += 1
    ans %= MOD

if cur_m % 2 == 0:
    print(ans)
else:
    if cur_p == len(P):
        ans *= M[cur_m]
        ans *= pow(P[cur_p - 1], MOD - 2, MOD)
        ans %= MOD
    elif cur_m == len(M):
        ans *= P[cur_p]
        ans *= pow(P[cur_m - 1], MOD - 2, MOD)
        ans %= MOD
    else:
        m1 = M[cur_m - 1]
        p1 = P[cur_p]
        m2 = M[cur_m]
        p2 = P[cur_p - 1]
        if p1 / m1 > m2 / p2:
            ans *= p1
            ans *= pow(m1, MOD - 2, MOD)
            ans %= MOD
        else:
            ans *= m2
            ans *= pow(p2, MOD - 2, MOD)
            ans %= MOD
    print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


P = []
M = []
zero = 0
for a in A:
    if a >= 0:
        P.append(a)
    elif a < 0:
        M.append(a)

ans = 1
if K == N:
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

ans = 1
if len(P) == 0 and K % 2 == 1:
    M.sort(reverse=True)
    for k in range(K):
        ans *= M[k]
        ans %= MOD
    print(ans)
    exit()

P.sort(reverse=True)
M.sort()
S = 1
LP = len(P)
LM = len(M)
cur_p = 0
cur_m = 0
cnt = 0
ans = 1
while cnt < K:
    if K - cnt == 1 or LM - cur_m <= 1:
        flag = 'p'
    elif LP - cur_p == 1:
        if (K - cnt) % 2 == 1:
            flag = 'p'
        else:
            flag = 'm'
    elif LP - cur_p == 0:
        flag = 'm'
    else:
        p1 = P[cur_p]
        p2 = P[cur_p + 1]
        m1 = M[cur_m]
        m2 = M[cur_m + 1]
        if p1 * p2 >= m1 * m2:
            flag = 'p'
        else:
            flag = 'm'
    
    if flag == 'p':
        ans *= P[cur_p]
        ans %= MOD
        cur_p += 1
        cnt += 1
    else:
        ans *= M[cur_m] * M[cur_m + 1]
        ans %= MOD
        cur_m += 2
        cnt += 2

print(ans)