Harryxun/stf_run huggingface dataset:
import copy
n, m = map( int, input().split() )
connect = []

for _ in range( n+1 ):
    connect.append( [ 0 ] * ( n+1 ) )

for _ in range( m ):
    a, b = map( int, input().split() )
    connect[ a ][ b ] = 1
    connect[ b ][ a ] = 1

guide = [ 0 ] * ( n+1 )
path = [ 0, 0 ] + [ m+1 ] * ( n-1 )
unvisited = [ a for a in range( 1, n+1 ) ]

def solve( a, unvisited ): # aに隣接したやつのguideをaにする．またそれのpathをpath[a]+1にする．
    for b in unvisited:
        if connect[a][b] == 1 and path[a] + 1 < path[b]:
            path[b] = path[a] + 1
            guide[b] = a
    for b in unvisited:
        if connect[a][b] == 1:
            next_unvisited = copy.deepcopy( unvisited )
            next_unvisited.remove( a )
            solve( b, list( next_unvisited)  )

solve( 1, list( unvisited ) )

if 0 not in guide[2:]:
    print( "Yes" )
    for i in range( 2, n+1 ):
        print( guide[i] )
else:
    print( "No" )


### FIXED CODE ###

####以下カンニング####
n, m = map( int, input().split() )
connect = {}

for _ in range( m ):
    a, b = map( int, input().split() )
    try:
        connect[ a ].append( b )
    except KeyError:
        connect[ a ] = [ b ]
    try:
        connect[ b ].append( a )
    except KeyError:
        connect[ b ] = [ a ]

queue = [ 1 ]
guide = [ -1 ] * ( n+1 )
visited = [ False ] * ( n+1 )

while queue:
    x = queue.pop(0)
    for y in connect[ x ]:
        if visited[ y ] == False:
            queue.append( y )
            guide[ y ] = x
            visited[ y ] = True

print( "Yes" )
for x in range( 2, n+1 ):
    print( guide[x] )
n , m = map(int, input().split())
a = list(map(int, input().split()))
print(max(n - sum(a)), -1)

### FIXED CODE ###

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

print(max(n - sum(a), - 1))
from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
y=0

for x in a:
  if y!=x and l%x!=0:
    g=gcd(l,x)
  y=x

l=lcm(*a)

for x in a:
  ans+=(l//x)%m

print(ans%m)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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


def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
'''
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g
'''
l=lcm(*a)

for x in a:
  ans+=l//x

print(ans%m)
import math

A,B,K=map(int,input().split())
gcd=math.gcd(A,B)
#print(gcd)
l=[]
for i in range(1,gcd+1):
    if gcd%i==0:
        l.append(i)
print(l[len(l)-K])

### FIXED CODE ###

import fractions

A,B,K=map(int,input().split())
gcd=fractions.gcd(A,B)
#print(gcd)
l=[]
for i in range(1,gcd+1):
    if gcd%i==0:
        l.append(i)
#print(l)
print(l[len(l)-K])
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

#a = Counter(A)
l_a = len(a)
if(l_a%2 == 0):
     print(l_a-1)
else:
    print(l_a)

### FIXED CODE ###

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

a = Counter(A)
l_a = len(a)
if(l_a%2 == 0):
     print(l_a-1)
else:
    print(l_a)
N = int(input())
L = []
for i in range(N):
  L.append((int(input),'a'))
for i in range(N):
  L.append((int(input),'b'))
L.sort()
res = 1
cc = 0
nowcol = None
mo = 1000000007
for i in range(2*N):
  if cc == 0:
    nowcol=L[i][1]
  if nowcol == L[i][1]:
    cc += 1
  else:
    res *= cc
    res %= mo
    cc -= 1
print(res)

### FIXED CODE ###

N = int(input())
L = []
for i in range(N):
  L.append((int(input()),'a'))
for i in range(N):
  L.append((int(input()),'b'))
L.sort()
res = 1
cc = 0
nowcol = None
mo = 1000000007
for i in range(2*N):
  if cc == 0:
    nowcol=L[i][1]
  if nowcol == L[i][1]:
    cc += 1
  else:
    res *= cc
    res %= mo
    cc -= 1
print(res)
if B < A:
    print("0")
elif B ==A:
    print("1")
else:
    while ans < B:
        ans += A
        ans -= 1
        c += 1
    print(c)

### FIXED CODE ###

import math
A,B  = list(map(int,input().split()))
ans  = 1
c = 0
if B ==1:
    print("0")
elif B <= A:
    print("1")
else:
    while ans < B:
        ans += A-1
        c += 1
    print(c)
a=list(map(input().split()))
b=list(map(input().split()))
if a[0]==b[0]:
  A=1
else:
  A=0
if a[1]==b[1]:
  B=1
else:
  B=0
if a[2]==b[2]:
  C=1
else:
  C=0
print(A+B+C)


### FIXED CODE ###

a=input()
b=input()
if a[0]==b[0]:
  A=1
else:
  A=0
if a[1]==b[1]:
  B=1
else:
  B=0
if a[2]==b[2]:
  C=1
else:
  C=0
print(A+B+C)
n = int(input())
ans = len(str(n))
for i in range(1, int(n**(1/2))+1):
  if n%i == 0:
    ans = min(ans, max(len(str(i)), len(str(n//i))))
print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
print((a + b) % 24)
from collections import Counter
n=int(input())
s_=input()
s=Couter(s_)
rgb = s['R'] * s['G'] * s['B']
cnt=0
for i in range(len(s_)):
  for j in range(i+1,len(s_)):
    h=j-i+j
    if h<n:
      if s_[i]!=s_[j] and s_[h]!=s_[j] and s_[i]!=s_[h]:
        cnt+=1

print(rgb-cnt)
    

### FIXED CODE ###


n=int(input())
s_=input()
r, g, b = s_.count("R"), s_.count("G"), s_.count("B")
rgb = r * g * b
cnt=0
for i in range(len(s_)):
  for j in range(i+1,len(s_)):
    h=j-i+j
    if h<n:
      if s_[i]!=s_[j] and s_[h]!=s_[j] and s_[i]!=s_[h]:
        cnt+=1

print(rgb-cnt)
def fact(x):
    if x == 0:
        return 1
    else:
        return x * fact(x - 1) % mod


mod = 10 ** 9 + 7

n = int(input())
s = input()
t = list(map(lambda x: 1 if x == 'B' else 0, s))
t = tuple((tt - df) % 2 for tt, df in zip(t, reversed(range(n * 2))))
# print(t)

zeros = 0
ans = 1
ones = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans *= zeros
        ans %= mod
        zeros -= 1
        ones += 1

if zeros > 0:
    ans = 0

ans *= fact(ones)
ans %= mod
print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)


def fact(x):
    if x == 0:
        return 1
    else:
        return x * fact(x - 1) % mod


mod = 10 ** 9 + 7

n = int(input())
s = input()
t = list(map(lambda x: 1 if x == 'B' else 0, s))
t = tuple((tt - df) % 2 for tt, df in zip(t, reversed(range(n * 2))))
# print(t)

zeros = 0
ans = 1
ones = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans *= zeros
        ans %= mod
        zeros -= 1
        ones += 1

if zeros > 0:
    ans = 0

ans *= fact(ones)
ans %= mod
print(ans)
n=int(input())
la=[]
for i in range(n):
  d=int(input())
  a=[list(map(int,input().split())) for dd in range(d)]
  la.append(a)
cnt=n
for r in range(n-1):
  for p in range(r+1,n):
    for aa in la[r]
      for bb in la[p]:
        if aa[0]==bb[0] and aa[1]!=bb[1]:
          cnt-=1
print(cnt)
                                     

### FIXED CODE ###

import itertools
n=int(input())
la=[]
for _ in range(n):
  d=int(input())
  for dd in range(d):
    x,y=map(int,input().split())
    la.append([_,x-1,y])
ans=0
for i in itertools.product([0,1],repeat=n):
  s=sum(list(i))
  for l in la:
    if i[l[0]]==1 and i[l[1]]!=l[2]:
      break
  else:
    ans=max(ans,s)
print(ans)
n, k = map(int, input().split())
p = list(map(int, input().split()))
nxt = 0
mx = []
for i in range(n):
    pex = (1+p[i])/2
    mx.append(pex+nxt)
    nxt = pex + nxt
ans = []
for i in range(n-k):
    ans.append(mx[i+k] - mx[i])
print(max(ans)+0.000000000001)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
nxt = 0
mx = []
for i in range(n):
    pex = (1+p[i])/2
    mx.append(pex+nxt)
    nxt = pex + nxt
if n == k:
    print(mx[-1])
else:
    ans = []
    for i in range(n-k):
        ans.append(mx[i+k] - mx[i])
    print(max(ans))
N=int(input())
H=list(map(int,input().split()))
c=0
C=[]

for i in range(N-1) :

    if N == 1 :

        break



    if H[i] >= H[i+1] :

        c+=1

    if i==len(H)-2 or H[i] < H[i+1]:

        C.append(c)

        c = 0

        
print(max(C))
    


### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
c=0
C=[0]

for i in range(N-1) :

    if H[i] >= H[i+1] :

        c+=1

    if i==N-2 or H[i] < H[i+1]:

        C.append(c)

        c = 0

print(max(C))
import sys

def stdin_parse_int():
    list = []
    for i in sys.stdin:
        list.append(int(i))
    return list

list = stdin_parse_int()
A = list[0]
B = list[1]
K = list[2]

if A > K:
    print(str(A-K) + " " + str(B))
elif A+B > K:
    print(str(0) + " " + str(A+B-K))
else:
    print("0 0")



### FIXED CODE ###

import sys

def stdin_parse_int():
    a = list(map(int,input().split()))
    return a

list = stdin_parse_int()
A = list[0]
B = list[1]
K = list[2]

if A > K:
    print(str(A-K) + " " + str(B))
elif A+B > K:
    print(str(0) + " " + str(A+B-K))
else:
    print("0 0")
n, k=mat(int, input().split())

ans=k*((k-1)**(n-1))

print(ans)

### FIXED CODE ###


def penki(a, b, c):
  if a==b and b==c:
    return 1
  elif a!=b and b!=c and c!=a:
    return 3
  else:
    return 2

a,b,c=map(int, input().split())
print(penki(a, b, c))
n = int(input())
nums = [int(i) for i in input().split()]

nums.sort_values(reverse=True)
print(sum(nums[0::2]) - sum(nums[1::2]))


### FIXED CODE ###

n = int(input())
nums = [int(i) for i in input().split()]

nums.sort(reverse=True)
print(sum(nums[0::2]) - sum(nums[1::2]))
n ,k = input().split();
n = int(n);
k = int(k);

H = list(map(int, input().split()));

#HPが多い敵を上からk体だけ減らす。
yowa = H.sort(reverse=True)[k+1:];

ans = sum(yowa);

print(ans);

### FIXED CODE ###

n ,k = input().split();
n = int(n);
k = int(k);

H = list(map(int, input().split()));

#HPが多い敵を上からk体だけ減らす。
H.sort(reverse=True);
yowa = H[k:];

ans = sum(yowa);

print(ans);
# import math
# import fractions
# import numpy as np
from scipy.misc import comb

MOD = 10 ** 9 + 7

# ゼロ埋め
# list = [0] * N

# 二次元配列
# [[inf, inf, inf], [inf, inf, inf]]
# dp = [[float('inf')] * (H + 1) for i in range(N + 1)]

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
 
p = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def solve(N, M, A):
    max = 0
    desc = sorted(A, reverse=True)

    for i in range(1, N):
        max += desc[i] * comb(N-i,  M-1, MOD)

    min = 0
    asc = sorted(A)
    for i in range(1, N):
        min += desc[i] * comb(N-i,  M-1, NOD)

    return int((max - min) % MOD)

# S = input()
# N = int(input())
N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = [int(input()) for _ in range(n)]
# A = []
# B = []
# for _ in range(N):
#     a, b = list(map(int, input().split()))
#     A.append(a)
#     B.append(b)

print(solve(N, M, A))


### FIXED CODE ###

MOD = 10 ** 9 + 7

def solve(N, K, A):
    A.sort()
    ans = 0
 
    for i in range(1, N):
        now = cmb(i, K - 1, MOD)
        ans += A[i] * now
 
    A.sort(reverse=True)
    for i in range(1, N):
        now = cmb(i, K - 1, MOD)
        ans += A[i] * (-now)
 
    return ans % MOD
 
 
# N = int(input())
# S = input()
N, K = map(int, input().split())
A = list(map(int, input().split()))

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


print(solve(N, K, A))
x = input()
ans = 0
y = x

for i in range(10 ** 18):
  y = 100 ** (1.01 * i)
  if y > x:
    ans += 1
    print(ans)
  	

### FIXED CODE ###

x = int(input())
y = 100
ans = 0

while y < x:
  ans += 1
  y = y * 101 // 100
  
print(ans)
# -*- coding: utf-8 -*-
a = int(input())
b = int(input())

if a > 8 or b > 8:
    print(': (')
else:
    print('Yay!')


### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())

if a > 8 or b > 8:
    print(':(')
else:
    print('Yay!')
n,k,q = map(int,input().split())
li = [k-q] * n
numli = [int(input()) for i in range(q)]
for a in numli:
    li[a-1] += 1
for i in li:
    if i > 0
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
li = [k-q] * n
numli = [int(input()) for i in range(q)]
for a in numli:
    li[a-1] += 1
for i in li:
    if i > 0:
        print("Yes")
    else:
        print("No")
import sys
n = int(input())
sys.setrecursionlimit(n)
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    graph[a].append((b, i))
    graph[b].append((a, i))

def DFS(node, p_node=-1, p_color=-1):
    color = 1
    for c_node, edge in graph[node]:
        if c_node==p_node:
            continue
        if color==p_color:
            color += 1
        ans[edge] = color
        DFS(c_node, node, color)
        color += 1
ans = [0]*(n-1)
DFS(0)
k = max(len(i) for i in graph)
print(k)
[print(i) for i in ans]

### FIXED CODE ###

import sys
n = int(input())
sys.setrecursionlimit(2*n)
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    graph[a].append((b, i))
    graph[b].append((a, i))

def DFS(node, p_node=-1, p_color=-1):
    color = 1
    for c_node, edge in graph[node]:
        if c_node==p_node:
            continue
        if color==p_color:
            color += 1
        ans[edge] = color
        DFS(c_node, node, color)
        color += 1
ans = [0]*(n-1)
DFS(0)
k = max(len(i) for i in graph)
print(k)
[print(i) for i in ans]
l = input()
for i in range(0, 5)
	print(l[i], end="")
for j in range(6, 13)
	print(l[j], end="")
for k in range(14, 19)
	print(l[k], end="")

### FIXED CODE ###

l = input()
for i in range(0, 5):
	print(l[i], end="")
print(" ", end="")
for j in range(6, 13):
	print(l[j], end="")
print(" ", end="")
for k in range(14, 19):
	print(l[k], end="")
n = int(input())
x = [list(input().split(""))for i in range(n)]

for i in range(n):
    x[i][1] = int(x[i][1])

test2 = sorted(x,key = lambda k :(k[0],-k[1]))

for i in range(n):
    print(x.index(test2[i])+1)

### FIXED CODE ###

n = int(input())
 
 
x = [list(input().split(" ")) for i in range(n)]
 
for i in range(n):
    x[i][1] = int(x[i][1])
 
test2 = sorted(x, key = lambda k:(k[0],-k[1]))
 
for i in range(n):
    print(x.index(test2[i]) + 1)
import heapq

INF = 10**15
n = int(input())
edges = [[] for _ in range(n)]
costs = [INF]*n
def dfs(current, prev, d):
    costs[current] = d
    for nex in edges[current]:
        if nex[0] == prev:
            continue
        dfs(nex[0], current, d+nex[1])

for i in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))

q, k = map(int, input().split())
k -= 1
dfs(k, -1, 0)

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

n = int(input())
edges = [[] for _ in range(n)]
costs = [-1]*n
def dfs(current):

    for nex, cost in edges[current]:
        if costs[nex] != -1:
            continue
        costs[nex] = costs[current] + cost
        dfs(nex)

for i in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))

q, k = map(int, input().split())
k -= 1
costs[k] = 0
dfs(k)

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)
print("22から25までの数値を入力して下さい")
D = int(input())

if D == 22:
    print("Christmas Eve Eve Eve")
    break
elif D == 23:
    print("Christmas Eve Eve")
    break
elif D == 24:
    print("Christmas Eve")
    break
elif D == 25:
    print("Christmas")
    break
else:
    print("22から25までの数値を入力して下さい")
    D = int(input())

### FIXED CODE ###

def christmasday():
    D = int(input())
    if D == 22:
        print("Christmas Eve Eve Eve")
    elif D == 23:
        print("Christmas Eve Eve")
    elif D == 24:
        print("Christmas Eve")
    elif D == 25:
        print("Christmas")
christmasday()
from math import gcd
from functools import reduce
from sys import exit

# O(A+N)解
MAX_A = 1000000
lowerst_prime = [0] * (MAX_A + 1) # 最小の素因数をいれる(2以上をみていけばいい)
primes = [] # MAX_A以下の素数の集合
count = [0] * (MAX_A + 1) # 約数として出てくる回数を数える
for i in range(2, MAX_A + 1): # 線形時間で処理してくれる
    if lowerst_prime[i] == 0:
        continue
    lowerst_prime[i] = i
    for p in primes:
        if i * p > MAX_A:
            break
        lowerst_prime[i * p] = p # p がi * p のもっとも小さな素因数となるときのみ更新されるので、線形時間アルゴリズムとなる
# 入力
N = int(input())
A = [*map(int, input().split())]
if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)
for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        if count[divide]:
            # A[x] % i == A[y] % i == 0 となるx != yが存在するので、i | gcd(x, y)となる
            print("setwise coprime")
            exit(0)
        count[divide] += 1
        while A[i] % divide == 0: # 割れるだけ割る
            A[i] //= divide
print("pairwise coprime")


### FIXED CODE ###

from math import gcd
from functools import reduce
from sys import exit

# O(NlogA+AloglogA)解
MAX_A = 1000000
lowerst_prime = [10**9] * (MAX_A + 1) # 最小の素因数をいれる(2以上をみていけばいい)
count = [0] * (MAX_A + 1) # 約数として出てくる回数を数える

for i in range(2, MAX_A + 1): # エラトステネスの篩
    if lowerst_prime[i] != 10**9:
        continue
    lowerst_prime[i] = i
    for j in range(i * i, MAX_A + 1, i): # i * iスタートでいいのは、i * bはbの約数でもあるため
        if lowerst_prime[j] == 10**9:
            lowerst_prime[j] = i
# 入力
N = int(input())
A = [*map(int, input().split())]

if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)

for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        count[divide] += 1
        while A[i] % divide == 0: # 割れるだけ割る
            A[i] //= divide

for i in range(MAX_A + 1):
    if count[i] >= 2:
        print("setwise coprime")
        exit(0)
print("pairwise coprime")
n = int(input())

if n[0] == 9:
  print("Yes")
elif n[1] == 9:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n = int(input())

if n == 19 or n == 29 or n == 39 or n == 49 or n == 59 or n == 69 or n == 79 or n == 89 or n == 91 or n == 92 or n == 93 or n == 94 or n == 95 or n == 96 or n == 97 or n == 98 or n == 99 :
  print("Yes")
else:
  print("No")
N, M = int(input().split())  # N個のスイッチ, M個の電球

# M個の電球がそれぞれどこのスイッチと繋がっているかを格納
SSS = [list(map(int, input().split()))[1:] for i in range(M)]
P = list(map(int, input().split()))

ans = 0

for i in range(1 << N):  # 2のN乗の値になる, bit全探索
    for mask in range(M):
        ans_2 = 0
        for s in SSS[mask]:
            if (1 << s-1) & i != 0:
                ans_2 += 1

        if ans_2 % 2 != P[m]:
            break
    else:
        ans += 1

print(ans)
        

### FIXED CODE ###

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

# 繋がってるスイッチの情報
S = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))

# print(S)
# print(P)

ans = 0

for i in range(1 << N):
    # print(i)
    for m in range(M):
        cnt = 0
        for s in S[m]:  # Sは繋がっているスイッチの情報
            if i & (1 << (s-1)) != 0:
                cnt += 1
        if cnt % 2 != P[m]:
            break
    else:
        ans += 1

print(ans)
a = input()
b = input()
c = input()

print("A" + b + "C")

### FIXED CODE ###

str = input()

print("A" + str[8] + "C")
MOD = 10 ** 9 + 7
it = lambda: list(map(int, input().strip().split()))

def solve():
    N, K = it()
    A = it()
    
    neg = []
    pos = []
    for i in range(N):
        if A[i] < 0:
            neg.append(A[i])
        elif A[i] > 0:
            pos.append(A[i])
    
    if not neg and not pos:
        return 0
    
    pos.sort()
    neg.sort(reverse=True)

    if not pos and K % 2 == 1:
        ans = 1
        for i in range(K):
            ans = ans * neg[i] % MOD
        return ans

    ans = 1
    i = 0
    j = 0
    for _ in range(K >> 1):
        if len(pos) >= 2 and len(neg) >= 2:
            if neg[-1] * neg[-2] >= pos[-1] * pos[-2]:
                ans = ans * neg.pop() % MOD * neg.pop() % MOD
            else:
                ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(pos) >= 2:
            ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(neg) >= 2:
            ans = ans * neg.pop() % MOD * neg.pop() % MOD
    
    if K % 2 == 1:
        if pos:
            ans = ans * pos.pop() % MOD
        else:
            ans = ans * neg.pop() % MOD
    return ans


if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

MOD = 10 ** 9 + 7
it = lambda: list(map(int, input().strip().split()))

def solve():
    N, K = it()
    A = it()
    
    zero = 0
    neg = []
    pos = []
    for i in range(N):
        if A[i] < 0:
            neg.append(A[i])
        elif A[i] > 0:
            pos.append(A[i])
        else:
            zero += 1
    
    if not neg and not pos:
        return 0
    
    pos.sort()
    neg.sort(reverse=True)

    if not pos and K % 2 == 1:
        if zero > 0:
            return 0

        ans = 1
        for i in range(K):
            ans = ans * neg[i] % MOD
        return ans

    ans = 1
    for _ in range(K >> 1):
        if len(pos) >= 2 and len(neg) >= 2:
            if neg[-1] * neg[-2] >= pos[-1] * pos[-2]:
                ans = ans * neg.pop() % MOD * neg.pop() % MOD
            else:
                ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(pos) >= 2:
            ans = ans * pos.pop() % MOD * pos.pop() % MOD
        elif len(neg) >= 2:
            ans = ans * neg.pop() % MOD * neg.pop() % MOD
        elif len(pos) == 1 and len(neg) == 1:
            ans = ans * pos.pop() % MOD * neg.pop() % MOD
        else:
            return 0
    
    if K % 2 == 1:
        if pos:
            ans = ans * pos.pop() % MOD
        elif neg:
            ans = ans * neg.pop() % MOD
        else:
            return 0
    if zero > 1 and ans < 0:
        return 0
    return ans


if __name__ == '__main__':
    print(solve())
K = input()

t = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(t[K + 1])

### FIXED CODE ###

K = int(input())

t = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(t[K - 1])
from itertools import groupby
n =int(input())

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n%i == 0:
      n //= i
      table.append(i)
      i += 1
  if n > 1:
    table.append(n)
  return table

from itertools import groupby
ans = 0
p = prime_decomposition(n)
for k,g in p:
  gn = len(list(g))
  for i in range(1,1000000000000):
    gn -= i
    if gn >= 0:
      ans += 1
    else:
      break
print(ans)

### FIXED CODE ###

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

from itertools import groupby
N = int(input())
P = prime_decomposition(N)
ans = 0
for v, g in groupby(P):
    n = len(list(g))
    for i in range(1, 100000):
        n -= i
        if n >= 0:
            ans += 1
        else:
            break
print(ans)
S = list(input())
dic = {"a":0,"b":0,"c":0}
for s in S:
  dic[s] += 1
if max(dic.value)<=min(dic.value)+1:
  print("YES")
else:
  print("NO")


### FIXED CODE ###

S = list(input())
dic = {"a":0,"b":0,"c":0}
for s in S:
  dic[s] += 1
if max(dic.values())<=min(dic.values())+1:
  print("YES")
else:
  print("NO")
N = int(raw_input())
print( N / 2 + (N % 2))

### FIXED CODE ###

N = int(input())
num = N + (N % 2)
print(int(num/2))