Harryxun/stf_run huggingface dataset:
# Surrounded Nodes
from collections import deque
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        c = 2**(N-1)
        for x in G[i]:
            if x != parent[i]:
                c -= 2**count[x]
        c -= 2**(N-count[i])
        c += len(G[i])-1
        ans += c
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)

### FIXED CODE ###

# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)
from fractions import gcd

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

limit = int((10**12 + 1)**0.5)
prime_table = [True] * (limit + 1)

for i in range(2, limit):
    if prime_table[i] is True:
        for j in range(i + i, limit, i):
            prime_table[j] = False

ans = set()
g = gcd(a, b)

for i in range(1, g + 1):
    if a % i == 0 and b % i == 0 and prime_table[i] is True:
        ans.add(i)

print(len(ans))


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


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

g = gcd(a, b)
num = g

ans = 1

for i in range(2, int(g ** 0.5) + 1):

    if num % i == 0:
        ans += 1
        while num % i == 0:
            num = num // i

if num != 1:
    ans += 1

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

A = [A[0]] + [b for a,b in zip(A,A[1:]) if a != b]

diff = [a-b for a,b in zip(A[1:],A)]
B = [A[0]] if diff[0] > 0 else []

for i,(d1,d2) in enumerate(zip(diff, diff[1:]),start=1):
    if d1*d2 < 0:
        B.append(A[i])
B.append(A[-1])
t = iter(B)
c = 1000
for a,b in zip(t,t):
    c = c//a*b + c%a

print(c)


### FIXED CODE ###

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

A = [A[0]] + [b for a,b in zip(A,A[1:]) if a != b]

if len(A) < 2:
    print(1000)
    exit()

diff = [a-b for a,b in zip(A[1:],A)]
B = [A[0]] if diff[0] > 0 else []

for i,(d1,d2) in enumerate(zip(diff, diff[1:]),start=1):
    if d1*d2 < 0:
        B.append(A[i])
B.append(A[-1])
t = iter(B)
c = 1000
for a,b in zip(t,t):
    c = c//a*b + c%a

print(c)
s = input()

n = s.index('B')

s.pop(n-1)
print(s)

### FIXED CODE ###

s = str(input())

ans = []

for i in range(len(s)):
    if s[i] == '1':
        ans.append('1')
    elif s[i] == '0':
        ans.append('0')
    elif s[i] == 'B':
        ans = ans[:-1]

print(''.join(ans))
from itertools import accumurate
N,M=map(int,input().split())
L = [0]*(N+1)
for _ in range(M):
  l,r = map(lambda x:int(x)-1,input().split())
  L[l]+=1
  L[r+1]+=1

L = list(accumurate(L))
print(L.count(M)) 

### FIXED CODE ###

from itertools import accumulate
N,M=map(int,input().split())
L = [0]*(N+1)
for _ in range(M):
  l,r = map(lambda x:int(x)-1,input().split())
  L[l]+=1
  L[r+1]-=1

L = list(accumulate(L))
print(L.count(M))
A,B = input().split("")
A = int(A)
B = int(B)
if A == B:
  print((A-1) * (B-1))
else:
  print((A-1)*B)

### FIXED CODE ###

A,B = input().split(" ")
A = int(A)
B = int(B)
print((A-1) * (B-1))
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(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
t = []
for i in range(x):
    for j in range(y):
        for l in (range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                t.append(a[i]+b[j]+c[l])
            else:
                break
t.sort(reverse=True)
for i in range(k):
    print(t[i])

### 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(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        ans.append(a[i]+b[j]+c[k])
      else:
        break
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
n = map(int, input())

print((n // 2 + n % 2) / n)
  

### FIXED CODE ###

n = int(input())

print((n // 2 + n % 2) / n)
##Prime Numbers
##16D8101008G Kojima Masayoshi 小嶋真義　2018.4.18

import numpy as np
import math

n=int(input())

A=np.empty((n))
B=np.zeros((n))

count=0

for i in range(n):
    A[i]=int(input())


for i in range(n):
    if A[i]==1:
        B[i]=1
    elif A[i]==2:
        B[i]=0
    elif A[i]%2==0 :
        B[i]=1
    else:
        for j in range(2,int(math.sqrt(A[i]))):
            if A[i]%j==0:
                B[i]=1 
                break



for i in range(n):
    if B[i]==0:
        count=count+1

print(count)




### FIXED CODE ###

from math import sqrt

n=int(input())

count=0

for i in range(n):
    x=int(input())
    if x==1:
        count=count+1
    elif x!=2 and x%2==0:
        count=count+1
    elif x==2 or x==3 or x==5:
        count=count
    else:
        for j in range(2,int(sqrt(x))+1): 
            if x%j==0:
                count=count+1
                break


print(n-count)
a,b=map(int,input().split())
c=a*b
if c%2==0:
  print(Even)
else:
  print(Odd)

### FIXED CODE ###

a,b=map(int,input().split())
c=a*b
if c%2==0:
  print("Even")
else:
  print("Odd")
# encoding: utf-8
import sys
# input = sys.stdin.readline
P = 10 ** 9 + 7

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

# molec = 1
# for i in range(K - 1):
#     molec = (molec * (i + 1)) % P

power = 10 ** 9 + 5
digits = []
for i in range(64):
    digits.append(power % 2)
    power >>= 1

def modinv(b):
    binv = 1
    val = b % P
    for i, digit in enumerate(digits):
        if digit == 1:
            binv = (binv * val) % P
        val = (val * val) % P
    # print("##", b, binv)
    return binv

molec = 1
tab_nck = [1]
for i in range(1, K - 1):
    molec = (molec * (K - i)) % P
    molec = (molec * modinv(i)) % P
    tab_nck.append(molec)
tab_nck.append(1)

molec = 1
tab_nck2 = [1]
for i in range(1, N - K + 1):
    molec = (molec * (N - K + 2 - i)) % P
    molec = (molec * modinv(i)) % P
    tab_nck2.append(molec)
tab_nck2.append(1)

# print("#", tab_nck)
# print("#", tab_nck2)

def nck(a, b):
    # a = K - 1
    return tab_nck[b]

def nck2(a, b):
    # a = N - K + + 1
    return tab_nck2[b]

for i in range(1, K + 1):
    ans = 1
    #
    ans = (ans * nck(K - 1, i - 1)) % P
    # print("#", nck(K - 1, i - 1))
    ans = (ans * nck2(N - K + i - 1, i)) % P
    # print("#", nck2(N - K + i - 1, i))
    #
    print(ans)

### FIXED CODE ###

# encoding: utf-8
import sys
# input = sys.stdin.readline
P = 10 ** 9 + 7

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

# molec = 1
# for i in range(K - 1):
#     molec = (molec * (i + 1)) % P

power = 10 ** 9 + 5
digits = []
for i in range(64):
    digits.append(power % 2)
    power >>= 1

def modinv(b):
    binv = 1
    val = b % P
    for i, digit in enumerate(digits):
        if digit == 1:
            binv = (binv * val) % P
        val = (val * val) % P
    # print("##", b, binv)
    return binv

molec = 1
tab_nck = [1]
for i in range(1, K - 1):
    molec = (molec * (K - i)) % P
    molec = (molec * modinv(i)) % P
    tab_nck.append(molec)
tab_nck.append(1)

molec = 1
tab_nck2 = [1]
for i in range(1, N - K + 1):
    molec = (molec * (N - K + 2 - i)) % P
    molec = (molec * modinv(i)) % P
    tab_nck2.append(molec)
tab_nck2.append(1)

# print("#", tab_nck)
# print("#", tab_nck2)

def nck(a, b):
    # a = K - 1
    if b < 0: return 0
    elif b > K - 1: return 0
    else: return tab_nck[b]

def nck2(a, b):
    # a = N - K + 1
    if b < 0: return 0
    elif b > N - K + 1: return 0
    else: return tab_nck2[b]

for i in range(1, K + 1):
    ans = 1
    #
    ans = (ans * nck(K - 1, i - 1)) % P
    ans = (ans * nck2(N - K + i - 1, i)) % P
    #
    print(ans)
t1,t2 = list(map(int, input().split()))
a1,a2 = list(map(int, input().split()))
b1,b2 = list(map(int, input().split()))
x=(a1-b1)*t1 + (a2-b2)*t2
if x == 0:
    print("infinity")
if x*(a1-b1) > 0:
    print(0)
else:
    s,t = divmod(abs((a1-b1)*t1), abs(x))
    if t:
        print(s*2+1)
    else:
        print(s*2)


### FIXED CODE ###

t1,t2 = list(map(int, input().split()))
a1,a2 = list(map(int, input().split()))
b1,b2 = list(map(int, input().split()))
x=(a1-b1)*t1 + (a2-b2)*t2
if x == 0:
    print("infinity")
elif x*(a1-b1) > 0:
    print(0)
else:
    s,t = divmod(abs((a1-b1)*t1), abs(x))
    if t:
        print(s*2+1)
    else:
        print(s*2)
def f(s,pre):
  if s=="":return 0
  if pre==s[0]:
    return f(s[2:],s[:2])+1
  else:return f(s[1:],s[0])+1
print(f(input(),""))

### FIXED CODE ###

s=input()
if len(s)<=2:
    print(len(set(list(s))));exit()
dp=[0]*(len(s)+ 1)
dp[0]=0
dp[1]=1
dp[2]=(len(set(list(s[:2]))))

for i in range(3,1+len(s)):
    dp[i]=(dp[i-1]+1) if s[i-1]!=s[i-2]else (dp[i-3]+2)
print(dp[-1])
import numpy as np
N=int(input())
a=[]
b=[]
xa=[]
xb=[]
y=[]
for i in range (0,N):
    c,d=(int(x) for x in input().split(" "))
    xa.append(c)
    xb.append(d)
     
z=np.argsort(xb)

for i in range (0,N):
    a.append(xa[z[i]])
    b.append(xb[z[i]])
for i in range (0,N):
    if i==0:
      	y.append(a[0])
    else:
      	y.append(a[i]+y[i-1])
def check(i,a,b):
    if b[i]>=y[i]:
        return True
    else:
        return False
def final_check(a,b,N):
    for i in range (0,N):
        if check(i,a,b)==False:
            return "No"
    return "Yes"
print (final_check(a,b,N))


### FIXED CODE ###

x=input()
def goodorbad(n):
    for i in range (0,3):
        if n[i]==n[i+1]:
            return "Bad\n"
    return "Good\n"
print (goodorbad(x))
S = int(list(input()))
N = len(S)
ans = 999
for i in range(0, N - 3):  #1 2 3 4 5 6 7 #0 1 2 3 4 5 6
	num = S[i] * 100 + S[i + 1] * 10 + S[i + 2]
	if ans > abs(num - 753):
		ans = abs(num - 753)
print(ans)

### FIXED CODE ###

s = input()
 
ans = 1000
for i in range(len(s)-2):
    ans = min(ans, abs(753-int(s[i:i+3])))
print(ans)
a=tuple(input())
len_a=len(a)
b=tuple(input())
len_b=len(b)
c=tuple(input())
len_c=len(c)
flag_ab=[True]*(2*(len_b+len_c)+1)
for i in range(len_a):
  for j in range(len_b):
    if a[i]!=b[j] and a[i]!='?' and b[j]!='?':
      flag_ab[i-j+(len_b+len_c)]=False
flag_ac=[True]*(2*(len_b+len_c)+1)
for i in range(len_a):
  for j in range(len_c):
    if a[i]!=c[j] and a[i]!='?' and c[j]!='?':
      flag_ac[i-j+(len_b+len_c)]=False
flag_bc=[True]*(2*(len_b+len_c)+1)
for i in range(len_b):
  for j in range(len_c):
    if b[i]!=c[j] and b[i]!='?' and c[j]!='?':
      flag_bc[i-j+(len_b+len_c)]=False
ans=len_a+len_b+len_c
left_a=0
for left_b in range(-(len_b+len_c),len_b+len_c+1):
  for left_c in range(-(len_b+len_c),len_b+len_c+1):
    if flag_ab[left_b-left_a+(len_b+len_c)] and flag_ac[left_c-left_a+(len_b+len_c)] and flag_bc[left_c-left_b]:
      right_a=left_a+len_a
      right_b=left_b+len_b
      right_c=left_c+len_c
      left=min(left_a,left_b,left_c)
      right=max(right_a,right_b,right_c)
      ans=min(ans,right-left)
print(ans)

### FIXED CODE ###

a=tuple(input())
len_a=len(a)
b=tuple(input())
len_b=len(b)
c=tuple(input())
len_c=len(c)
flag_ab=[True]*20000
for i in range(len_a):
  for j in range(len_b):
    if a[i]!=b[j] and a[i]!='?' and b[j]!='?':
      flag_ab[i-j+10000]=False
flag_ac=[True]*20000
for i in range(len_a):
  for j in range(len_c):
    if a[i]!=c[j] and a[i]!='?' and c[j]!='?':
      flag_ac[i-j+10000]=False
flag_bc=[True]*20000
for i in range(len_b):
  for j in range(len_c):
    if b[i]!=c[j] and b[i]!='?' and c[j]!='?':
      flag_bc[i-j+10000]=False
ans=len_a+len_b+len_c
left_a=0
for left_b in range(-(len_b+len_c),len_b+len_c+1):
  for left_c in range(-(len_b+len_c),len_b+len_c+1):
    if flag_ab[left_b-left_a+10000] and flag_ac[left_c-left_a+10000] and flag_bc[left_c-left_b+10000]:
      right_a=left_a+len_a
      right_b=left_b+len_b
      right_c=left_c+len_c
      left=min(left_a,left_b,left_c)
      right=max(right_a,right_b,right_c)
      ans=min(ans,right-left)
print(ans)
#3
#8 12 40
n=int(input())
ai=list(map(int(),input.split()))
        
for a in ai:
  count =0
  while a%2==0 :
    count+=1
    a/=2
    b.append(count)
print(min(b))


### FIXED CODE ###

#3
#8 12 40
n=int(input())
ai=list(map(int,input().split()))
b=[]
for a in ai:
  count =0
  while a%2==0 :
    count+=1
    a/=2
  b.append(count)
print(min(b))
import math

N, H = map(int, input().split())
A = []
B = []

for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
A = A[::-1]
a_max = A[0]

B.sort()
B = B[::-1]

attack = 0
idx = 0

while B[idx] > a_max:
    H -= B[idx]
    attack += 1
    idx += 1
    if H <= 0:
        print(attack)
        break

if H > 0:
    attack += math.ceil(H / a_max)
    print(attack)

### FIXED CODE ###

import math

N, H = map(int, input().split())
A = []
B = []

for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

a_max = max(A)

B = sorted([x for x in B if x > a_max], reverse = True)

attack = 0

for damage in B:
    H -= damage
    attack += 1
    if H <= 0:
        break

if H > 0:
    attack += math.ceil(H / a_max)

print(attack)
n = int(input())
print((n*(n-1)//2)

### FIXED CODE ###

n = int(input())
print((n*(n-1))//2)
A = map(int, input().split())

if A + B < C + D:
    print('Left')
elif A + B == C + D:
    print('Balanced')
else:
    print('Right')


### FIXED CODE ###

A, B, C, D = map(int, input().split())

if A + B > C + D:
    print('Left')
elif A + B == C + D:
    print('Balanced')
else:
    print('Right')
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
sat=sum(b)
for i in range(n-1):
  if a[i+1]=a[i]+1:
    sat+=c[i]
print(sat)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
sat=sum(b)
for i in range(n-1):
  if a[i+1]==a[i]+1:
    sat+=c[a[i]-1]
print(sat)
def search(m,n,l): //startCは常に満たす、stopCは常に満たさない
  if l[0]<=m: return 0
  elif l[n-1]>m: return n
  startC,stopC=0,n
  while startC-stopC+1!=0:
    if l[(stopC-startC)>>1]>m:
      stopC=startC+(stopC-startC)>>1
    else:
      startC+=(stopC-startC)>>1
  return stopC

n=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
ans=0
for i in range(n-2):
  for j in range(1,n-i-1):
    ans+=search(l[i]-l[j+i+1],n,l[j+i+2]) //l[i]-l[j]<l[ans]を満たす最小のansを求める

### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n-1,1,-1):
  for j in range(i-1,0,-1):
    ans+=j-bisect.bisect_left(l,l[i]-l[j]+1,hi=j)
print(ans)
from itertools import accumulate

N, M, K = map(int, input().split())
a = list(accumulate(int(i) for i in input().split(), initial=0))
b = list(accumulate(int(i) for i in input().split(), initial=0))

cnt = 0
best0 = M
for i in range(N+1):
    ai = a[i]
    for j in range(best0, -1, -1):
        bj = b[j]
        if ai + bj <= K:
            cnt = max(cnt, i + j)
            best0 = j
            break

print(cnt)

### FIXED CODE ###

from itertools import accumulate

N, M, K = map(int, input().split())
A = list(accumulate(int(i) for i in input().split()))
B = list(accumulate(int(i) for i in input().split()))

a,b = [0],[0]
for ai in A:
    a.append(ai)
for bj in B:
    b.append(bj)

cnt = 0
best0 = M
for i in range(N+1):
   ai = a[i]
   for j in range(best0, -1, -1):
       bj = b[j]
       if ai + bj <= K:
           cnt = max(cnt, i + j)
           best0 = j
           break

print(cnt)
def main ():
N = int(input())
A = list(map(int,input().split()))
if 0 in A: print (0)
return
prod = 1 for a in A:
prod *= a
if prod > 1000000000000000000:
print(-1) return
print(prod) main ()


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split(' ')))

res = 1
for a in A:
    res = min(res*a, 10**18 + 1)
if res == 10**18 + 1: print(-1)
else: print(res)
N = input()

L = [2, 1]

if N == 1:
  print(1)
else:
  i = 1
  while i < N:
    L.append(L[i] + L[i-1])
    i += 1
  print(L[-1])

### FIXED CODE ###

N = int(input())
 
L = [2, 1]
 
if N == 1:
  print(1)
else:
  i = 1
  while i < N:
    L.append(L[i] + L[i-1])
    i += 1
  print(L[-1])
S = input()
T = input()

countbox=[]
for n in range(len(S)-2-len(T)+1):
    count =0
    for i in range(len(T)):
        if T[i] != S[i+n+1]:
            count+=1
    countbox.append(count)
print(min(countbox))


### FIXED CODE ###

S = input()
T = input()

if len(S)==len(T):
    count=0
    for i in range(len(T)):
        if T[i] != S[i]:
            count+=1
    print(count)

else:
    countbox=[]
    for n in range(len(S)-len(T)+1):
        count =0
        for i in range(len(T)):
            if T[i] != S[i+n]:
                count+=1
        countbox.append(count)
    print(min(countbox))
n, m = map(int, input().split())
favFood = [input().split() for i in range(n)]
for i in favFood:
    del i[:1]

if not(n == 1):
    count = 0
    for i in range(1, m):
        check = True
        for j in range(n):
            if not (str(i) in favFood[j]):
                check = False
        if check:
            count += 1
    print(count)

else:
    print(len(favFood))



### FIXED CODE ###

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

if b % a == 0:
    print(a + b)
else:
    print(b - a)
import sys
from math import cos, radians, pi, sqrt
import numpy as np

head = input().split()

N = int(head[0])
M = int(head[1])
inputs = [input() for i in range(M)]

vector = np.zeros((N, N))
for i in range(0, M):
	param = inputs[i].split()
	A = int(param[0])
	B = int(param[1])
	vector[A-1:A,B-1:B] = 1
	vector[B-1:B,A-1:A] = 1

depth = np.zeros((1, N))
que = [0]

while not que == []:
	room = que[0]
	que.pop(0)
	search = np.where(vector[room:room+1]==1)[1]
	for next_room in search:
		if not depth[:,next_room:next_room+1] == 0 or next_room == 0:
			continue
		depth[:,next_room:next_room+1] = depth[:,room:room+1]+1
		que.append(next_room)

if 0 in depth[:,1:][0]:
	print("No")
else:
	print("Yes")
	for dep in depth[:,1:][0]:
		print(np.where(depth==dep-1)[1][0]+1)


### FIXED CODE ###

n,m = map(int,input().split())
visited = [-1 for _ in range(n+1)]
visited[1] = 0
will = []
root = [[] for _ in range(n+1)] 
for i in range(m):
    a,b = map(int,input().split())
    root[a].append(b)
    root[b].append(a)

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])
N, K, *A = map(int, open(0).read().split())
MOD = 10 ** 9 + 7

s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(abs(v) for v in A)
    for i in range(L):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort()
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop() % MOD
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop() % MOD
        p.append(x)
        
    p.sort(reverse=True)
    for i in range(K // 2):
        ans *= p[i]
    
print(ans)



### FIXED CODE ###

N, K, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
s = []  # v >= 0
t = []  # v < 0
for i in range(N):
    if A[i] < 0:
        t.append(A[i])
    else:
        s.append(A[i])
        
ok = False  # ans > 0
if len(s) > 0:
    if N == K:
        ok = len(t) % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    x = sorted(A, key=lambda x: abs(x))
    for i in range(K):
        ans = ans * x[i] % MOD
else:
    s.sort()
    t.sort(key=lambda x: abs(x))
    if K % 2 == 1:
        ans = ans * s.pop() % MOD
        
    p = []
    while len(s) >= 2:
        x = s.pop() * s.pop()
        p.append(x)
    
    while len(t) >= 2:
        x = t.pop() * t.pop()
        p.append(x)

    p.sort(reverse=True)
    for i in range(K // 2):
        ans = ans * p[i] % MOD
    
print(ans)
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
dic_s = {}
for i in range(N):
    s = "".join(sorted(input()))
    if s in dic_s:
        dic_s[s] += 1
    else:
        dic_s[s] = 1
counter = 0
for key,value in dic_s.items():
    counter += combinations_count(value,2)
print(counter)

### FIXED CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
dic_s = {}
for i in range(N):
    s = "".join(sorted(input()))
    if s in dic_s:
        dic_s[s] += 1
    else:
        dic_s[s] = 1
counter = 0
for key,value in dic_s.items():
    if value >1:
        counter += combinations_count(value,2)
print(counter)
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
flag = True
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
     if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = []
for tag in list1:
    matched_list+=filter(lambda str: str == tag, nlist)
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

### FIXED CODE ###

import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = list(set(list1) & set(nlist))
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
# D - I hate Factorization
def meet_condition(i, j):
	pi = pows[i]
	pj = pows[j]
	
	if pi - pj == x:
		return i, j
	elif pi + pj == x:
		return i, -j


pows = []

for i in range(100):
	pows.append(pow(i, 5))

x = int(input())

for i in range(len(pows)):
	for j in range(len(pows)):
		if meet_condition(i, j) != None:
			a, b = meet_condition(i, j)
			print(a, b)
			sys.exit()

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - I hate Factorization
def meet_condition(i, j):
	pi = pows[i]
	pj = pows[j]
	
	if pi - pj == x:
		return i, j
	elif pi + pj == x:
		return i, -j


pows = []

for i in range(200):
	pows.append(pow(i, 5))

x = int(input())

for i in range(len(pows)):
	for j in range(len(pows)):
		if meet_condition(i, j) != None:
			a, b = meet_condition(i, j)
			print(a, b)
			exit()