AtCoder Beginner Contest 173 - Multiplication 4

Given are N integers A_1,\ldots,A_N.
We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.
Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

-----Constraints-----
 - 1 \leq K \leq N \leq 2\times 10^5
 - |A_i| \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 \ldots A_N

-----Output-----
Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).

-----Sample Input-----
4 2
1 2 -3 -4

-----Sample Output-----
12

The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.

Difficulty: MEDIUM

Starter code:

Solutions:
(N, K, *A) = map(int, open(0).read().split())
MOD = 10 ** 9 + 7
s = []
t = []
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(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)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
(mia, pla) = ([], [])
for ai in a:
	if ai < 0:
		mia.append(ai)
	elif ai >= 0:
		pla.append(ai)
mia.sort(reverse=True)
pla.sort()
cnt = 1
if len(pla) == 0 and k % 2 == 1:
	for i in mia[:k]:
		cnt = cnt * i % mod
else:
	while k > 0:
		if k == 1 or len(mia) <= 1:
			if len(pla) == 0:
				cnt *= mia.pop()
			elif len(pla) > 0:
				cnt *= pla.pop()
			k -= 1
		elif len(pla) <= 1:
			cnt *= mia.pop() * mia.pop()
			k -= 2
		elif len(pla) >= 2 and len(mia) >= 2:
			if pla[-1] * pla[-2] > mia[-1] * mia[-2]:
				cnt *= pla.pop()
				k -= 1
			elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
				cnt *= mia.pop() * mia.pop()
				k -= 2
		cnt %= mod
print(cnt)


import datetime
import string
import re
import math

def isort(list, _beg, _end):
	if _beg < _end:
		beg = _beg
		end = _end
		pivot = abs(list[int((beg + end) / 2)])
		while True:
			while abs(list[beg]) < pivot:
				beg += 1
			while abs(list[end]) > pivot:
				end -= 1
			if beg <= end:
				tmp = list[beg]
				list[beg] = list[end]
				list[end] = tmp
				beg += 1
				end -= 1
			else:
				break
		isort(list, _beg, end)
		isort(list, beg, _end)

def searchByBool(list):
	for i in range(len(list)):
		if check(list[i]):
			return i
	return -1

def check(num):
	if num >= 0:
		return True
	else:
		return False
sp = list(map(int, input().split()))
N = sp[0]
K = sp[1]
alist = list(map(int, input().split()))
klist = []
isK = True
isort(alist, 0, len(alist) - 1)
alist.reverse()
numMinus = 0
for i in range(K):
	if check(alist[i]) == False:
		numMinus += 1
if numMinus % 2 == 0:
	isK = False
if isK and K < N:
	_right = -1
	_left = -1
	for right in range(K, N):
		if check(alist[K - 1]) != check(alist[right]):
			_right = right
			break
	for left in range(K):
		if check(alist[K - 1 - left]) != check(alist[K]):
			_left = left
			break
	isK = False
	if _right != -1 and _left != -1:
		if abs(alist[K - 1 - left] * alist[_right]) < abs(alist[K - 1] * alist[K]):
			alist[K - 1 - _left] = alist[K]
		else:
			alist[K - 1] = alist[_right]
	elif _right == -1 and _left != -1:
		alist[K - 1 - _left] = alist[K]
	elif _right != -1 and _left == -1:
		alist[K - 1] = alist[_right]
	else:
		isK = True
if isK:
	alist.reverse()
klist = alist[0:K]
multi = klist[0]
for i in range(1, K):
	multi *= klist[i]
	multi = multi % 1000000007
print(multi)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = sorted(a, reverse=True)
mod = 10 ** 9 + 7
ans = 1
if k % 2 == 1 and s[0] < 0:
	for i in range(k):
		ans = ans * s[i] % mod
	print(ans)
	return
l = 0
r = n - 1
if k % 2 == 1:
	ans = ans * s[l]
	l += 1
for _ in range(k // 2):
	ml = s[l] * s[l + 1]
	mr = s[r] * s[r - 1]
	if ml > mr:
		ans = ans * ml % mod
		l += 2
	else:
		ans = ans * mr % mod
		r -= 2
print(ans)


MOD = 10 ** 9 + 7
(n, k) = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
m = list(filter(lambda x: x < 0, a))
p = list(filter(lambda x: x > 0, a))
m.sort()
p.sort(reverse=True)
if len(p) + len(m) < k:
	print(0)
	exit()
if len(p) + len(m) == k:
	ans = 1
	for p_ in p:
		ans = ans * p_ % MOD
	for q_ in m:
		ans = ans * q_ % MOD
	print(ans)
	exit()
if len(p) == 0 and k % 2 == 1:
	ans = 1
	for i in range(k):
		ans = ans * m[-i - 1] % MOD
	if 0 in a:
		ans *= 0
	print(ans)
	exit()
(i, j) = (0, 0)
if k % 2 == 1:
	d = p.pop(-1)
m.append(0)
m.append(0)
p.append(0)
p.append(0)
ans = 1
for c in range(k // 2):
	if m[i] * m[i + 1] >= p[j] * p[j + 1]:
		ans = ans * m[i] * m[i + 1] % MOD
		i += 2
	else:
		ans = ans * p[j] * p[j + 1] % MOD
		j += 2
if k % 2 == 1:
	ans = ans * max(p[j], d) % MOD
if ans > MOD:
	ans -= MOD
print(ans)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
flag = 0
A.sort()
tmp1 = 1
tmp2 = 1
l = 0
r = n - 1
if k % 2 == 1:
	tmp1 = A[-1] % mod
	r -= 1
	if A[-1] < 0:
		flag = 1
for i in range(k // 2):
	vl = A[l] * A[l + 1]
	vr = A[r] * A[r - 1]
	if max(vl, vr) < 0:
		flag = 1
	if vl > vr:
		l += 2
		tmp1 *= vl
	else:
		r -= 2
		tmp1 *= vr
	tmp1 %= mod
from bisect import bisect_right
idx = bisect_right(A, 0)
if idx == n:
	idx -= 1
l = max(0, idx - 1)
r = idx
for i in range(k):
	vl = A[l] if l >= 0 else mod
	vr = A[r] if r < n else mod
	if abs(vl) < abs(vr) or r == n:
		l -= 1
		tmp2 *= vl
	else:
		r += 1
		tmp2 *= vr
	tmp2 %= mod
if flag == 0:
	print(tmp1)
else:
	print(tmp2)


MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
S = []
T = []
for a in A:
	if a < 0:
		T.append(a)
	else:
		S.append(a)
lenS = len(S)
lenT = len(T)
ok = False
if lenS > 0:
	if N == K:
		ok = lenT % 2 == 0
	else:
		ok = True
else:
	ok = K % 2 == 0
ans = 1
if not ok:
	A.sort(key=lambda x: abs(x))
	for i in range(K):
		ans *= A[i]
		ans %= MOD
else:
	S.sort()
	T.sort(reverse=True)
	if K % 2 == 1:
		ans *= S.pop()
	P = []
	while len(S) >= 2:
		x = S.pop()
		x *= S.pop()
		P.append(x)
	while len(T) >= 2:
		x = T.pop()
		x *= T.pop()
		P.append(x)
	P.sort(reverse=True)
	for i in range(K // 2):
		ans *= P[i]
		ans %= MOD
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
neg_a = sorted([a for a in A if a < 0], reverse=True)
pos_a = sorted([a for a in A if a >= 0])
ans = 1
if len(pos_a) == 0 and K % 2 == 1:
	for a in neg_a[:K]:
		ans = ans * a % MOD
	print(ans)
	exit()
while K > 0:
	if K == 1 or len(neg_a) <= 1:
		if len(pos_a) == 0:
			ans *= neg_a.pop()
		elif len(pos_a) > 0:
			ans *= pos_a.pop()
		K -= 1
	elif len(pos_a) <= 1:
		ans *= neg_a.pop() * neg_a.pop()
		K -= 2
	elif pos_a[-1] * pos_a[-2] > neg_a[-1] * neg_a[-2]:
		ans *= pos_a.pop()
		K -= 1
	else:
		ans *= neg_a.pop() * neg_a.pop()
		K -= 2
	ans %= MOD
print(ans)


def solve():
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()), reverse=True)
	mod = 10 ** 9 + 7
	l = 0
	r = n - 1
	ans = 1
	if k % 2 == 1:
		ans = a[0]
		l = 1
	if ans < 0:
		mul = 1
		for i in range(k):
			mul = mul * a[i] % mod
		return mul
	for i in range(k // 2):
		l_mul = a[l] * a[l + 1]
		r_mul = a[r] * a[r - 1]
		if l_mul >= r_mul:
			ans = ans * l_mul % mod
			l += 2
		else:
			ans = ans * r_mul % mod
			r -= 2
	return ans
print(solve())


(n, k) = map(int, input().split())
a = [0] * n
a = list(map(int, input().split()))
a = sorted(a)
mod = 10 ** 9 + 7
ans = 1
if k % 2 == 0 or a[-1] >= 0:
	mlt1 = a[0] * a[1]
	mlt2 = a[-2] * a[-1]
	l = 0
	r = -1
	for i in range(k // 2):
		if mlt1 >= mlt2:
			ans *= mlt1 % mod
			l += 2
			if l <= n - 2:
				mlt1 = a[l + 1] * a[l]
		else:
			ans *= mlt2 % mod
			r -= 2
			if r >= -n + 1:
				mlt2 = a[r - 1] * a[r]
		ans %= mod
	if k % 2 == 1:
		ans *= a[r]
		ans %= mod
else:
	for i in range(k):
		ans *= a[n - 1 - i]
		ans %= mod
print(ans)


(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
X = sorted([a for a in A if a >= 0])
Y = sorted([a for a in A if a < 0], key=lambda x: abs(x))
if 2 * (min(K, len(Y)) // 2) + len(X) >= K:
	ans = 1
	if K % 2 == 1:
		ans *= X.pop()
		K -= 1
	XX = [x1 * x2 for (x1, x2) in zip(*[iter(X[::-1])] * 2)]
	YY = [y1 * y2 for (y1, y2) in zip(*[iter(Y[::-1])] * 2)]
	ZZ = sorted(XX + YY)
	for i in range(K // 2):
		ans *= ZZ.pop()
		ans %= MOD
	print(ans)
else:
	ans = 1
	Z = sorted(X + Y, key=lambda x: abs(x), reverse=True)
	for i in range(K):
		ans *= Z.pop()
		ans %= MOD
	print(ans)


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
K = k
(B, C) = ([], [])
for i in A:
	if i >= 0:
		B.append(i)
	else:
		C.append(i)
B.sort()
C.sort(key=lambda x: abs(x))
(ans, flag) = (1, 1)
while k != 0:
	if k >= 2:
		point = 0
		if len(B) >= 2 and len(C) >= 2:
			if B[-1] * B[-2] > C[-1] * C[-2]:
				ans *= B.pop()
				point = 1
			else:
				ans *= C.pop() * C.pop()
		elif len(B) >= 2:
			ans *= B.pop() * B.pop()
		elif len(C) >= 2:
			ans *= C.pop() * C.pop()
		else:
			flag = 0
		k -= 2 - point
	else:
		if len(B) >= 1:
			ans *= B.pop()
		else:
			flag = 0
		k -= 1
	ans %= mod
if flag:
	print(ans)
else:
	ans = 1
	A = sorted(A, key=lambda x: abs(x))
	for i in range(K):
		ans *= A[i]
		ans %= mod
	print(ans)


MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
sign = dict({-1: 0, 0: 0, 1: 0})
for a in A:
	if a < 0:
		sign[-1] += 1
	elif a > 0:
		sign[1] += 1
	else:
		sign[0] += 1
if sign[1] == 0 and K % 2 != 0:
	A.sort(reverse=True)
	ans = 1
	for i in range(K):
		ans *= A[i]
		ans %= MOD
elif sign[1] == 0 and K % 2 == 0:
	A.sort()
	ans = 1
	for i in range(K):
		ans *= A[i]
		ans %= MOD
else:
	A.sort()
	ans = 1
	(i, j) = (0, N - 1)
	while K > 0:
		if K > 1 and A[i] * A[i + 1] >= A[j] * A[j - 1]:
			ans *= A[i] * A[i + 1]
			ans %= MOD
			i += 2
			K -= 2
		else:
			ans *= A[j]
			ans %= MOD
			j -= 1
			K -= 1
print(ans)


(n, k) = map(int, input().split())
(*A,) = map(int, input().split())
p = 10 ** 9 + 7
A.sort()
ans = 1
if A[n - 1] <= 0 and k % 2 == 1:
	for i in range(k):
		ans *= A[n - 1 - i]
		ans %= p
	print(ans)
	exit()
i = 0
j = n - 1
if k % 2 == 1:
	ans *= A[j]
	ans %= p
	j -= 1
	k -= 1
for _ in range(k // 2):
	left = A[i] * A[i + 1]
	right = A[j] * A[j - 1]
	if left > right:
		ans *= left
		ans %= p
		i += 2
	else:
		ans *= right
		ans %= p
		j -= 2
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
plus = []
minus = []
for i in a:
	if i >= 0:
		plus.append(i)
	if i < 0:
		minus.append(-i)
plus.sort(reverse=True)
minus.sort(reverse=True)
ans = 1
if k == n:
	for x in a:
		ans = ans * x % mod
else:
	(i, j) = (0, 0)
	if k % 2 == 1:
		if len(plus) != 0:
			ans = plus[0]
			i += 1
		else:
			minus.sort()
			ans = -minus[0]
			j += 1
	while i + j != k:
		x_p = plus[i] * plus[i + 1] if i < len(plus) - 1 else 0
		x_m = minus[j] * minus[j + 1] if j < len(minus) - 1 else 0
		if x_p > x_m:
			ans = ans * x_p % mod
			i += 2
		else:
			ans = ans * x_m % mod
			j += 2
print(ans)


import numpy as np
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
if N == K:
	ans0 = 1
	for a in A:
		ans0 = ans0 * a % MOD
	print(ans0)
	return
A = sorted(A)
if K % 2 == 1 and A[-1] < 0:
	ans1 = 1
	for a in A[N - K:N]:
		ans1 = ans1 * a % MOD
	print(ans1)
	return
A = sorted(A, key=lambda x: abs(x), reverse=True)
AA = [np.sign(i) for i in A]
ansA = 1
for a in A[0:K]:
	ansA = ansA * a % MOD
ansAA = AA[0:K].count(-1) % 2
if ansA == 0 or ansAA == 0:
	print(ansA)
	return
B1 = A[0:K]
C1 = A[0:K]
B2 = sorted(A[K:N])
Bp = [i for i in A[0:K] if i > 0]
Bm = [i for i in A[0:K] if i < 0]
if B2[0] > 0:
	B2.insert(0, 0)
if B2[-1] < 0:
	B2.insert(-1, 0)
if not Bp:
	Bp.insert(0, B1[-1])
if not Bm:
	Bm.insert(0, B1[0])
B1.remove(Bp[-1])
B1.append(min(B2[0], 0))
ansB = 1
for a in B1[0:K]:
	ansB = ansB * a % MOD
C1.remove(Bm[-1])
C1.append(max(B2[-1], 0))
ansC = 1
for a in C1[0:K]:
	ansC = ansC * a % MOD
BB1 = [np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1) % 2
BB2 = [np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1) % 2
if ansBB1 == 1:
	print(ansC)
	return
if ansBB2 == 1:
	print(ansB)
	return
if abs(Bp[-1] * B2[-1]) - abs(Bm[-1] * B2[0]) >= 0:
	print(ansC)
else:
	print(ansB)


MOD = 10 ** 9 + 7
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 1
if N == K:
	for a in A:
		ans = ans * a % MOD
	print(ans)
	return
minus = []
plus = []
for a in A:
	if a < 0:
		minus.append(a)
	else:
		plus.append(a)
if len(minus) == N:
	if K % 2 == 0:
		A.sort()
	else:
		A.sort(reverse=True)
	for i in range(K):
		ans = ans * A[i] % MOD
	print(ans)
	return
minus.sort(reverse=True)
plus.sort()
if K % 2:
	ans *= plus.pop()
B = []
while len(minus) > 1:
	a = minus.pop()
	b = minus.pop()
	B.append(a * b)
while len(plus) > 1:
	a = plus.pop()
	b = plus.pop()
	B.append(a * b)
B.sort()
for i in range(K // 2):
	ans = ans * B.pop() % MOD
print(ans)


from functools import reduce

def solve(*args: str) -> str:
	(n, k) = list(map(int, args[0].split()))
	A = sorted(map(int, args[1].split()))
	mod = 10 ** 9 + 7
	if n == k:
		return str(reduce(lambda a, b: a * b % mod, A, 1))
	if k % 2 and A[-1] < 0:
		return str(reduce(lambda a, b: a * b % mod, A[n - k:], 1))
	(l, r) = (0, n - 1)
	count = 0
	ret = 1
	if k % 2:
		ret *= A[-1]
		r -= 1
		count += 1
	while count < k - 1:
		pos = max(0, A[r] * A[r - 1])
		neg = max(0, A[l] * A[l + 1])
		if pos <= neg:
			ret *= neg
			l += 2
		else:
			ret *= pos
			r -= 2
		ret %= mod
		count += 2
	return str(ret % mod)

def __starting_point():
	print(solve(*open(0).read().splitlines()))
__starting_point()


mod = 10 ** 9 + 7
(num, k) = map(int, input().rstrip().split())
mai = list(map(int, input().rstrip().split()))
main = sorted(mai, key=abs, reverse=True)
result = 1

def findplus_plus(x):
	for i in range(x, len(main)):
		if main[i] >= 0:
			return main[i]
	return ''

def findplus_minus(x):
	for i in range(x, len(main)):
		if main[i] < 0:
			return main[i]
	return ''

def findminus_plus(x):
	for i in range(x - 1, -1, -1):
		if main[i] >= 0:
			return main[i]
	return ''

def findminus_minus(x):
	for i in range(x - 1, -1, -1):
		if main[i] < 0:
			return main[i]
	return ''
if num == k:
	for i in main:
		result *= i
		result %= mod
elif sorted(main)[len(sorted(main)) - 1] < 0:
	if k % 2 == 0:
		for i in range(k):
			result *= main[i]
			result %= mod
	else:
		for i in range(len(main) - 1, len(main) - 1 - k, -1):
			result *= main[i]
			result %= mod
else:
	count = 0
	for i in range(k):
		if main[i] < 0:
			count += 1
		result *= main[i]
		result %= mod
	if count % 2 == 1:
		minplus = findminus_plus(k)
		minminus = findminus_minus(k)
		maxplus = findplus_plus(k)
		maxminus = findplus_minus(k)
		if type(maxplus) == type(''):
			plusplus = -1
			minusminus = minminus * maxminus
		elif type(maxminus) == type('') or type(minplus) == type(''):
			minusminus = -1
			plusplus = 0
		else:
			minusminus = minminus * maxminus
			plusplus = minplus * maxplus
		if plusplus > minusminus:
			main.remove(minminus)
			result = 1
			for i in range(k - 1):
				result *= main[i]
				result %= mod
			result *= maxplus
		elif plusplus <= minusminus:
			main.remove(minplus)
			result = 1
			for i in range(k - 1):
				result *= main[i]
				result %= mod
			result *= maxminus
print(result % mod)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random, resource
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	(n, k) = LI()
	a = sorted(LI())
	r = 1
	i = n - 1
	j = 0
	if k % 2 == 1:
		r = a[i]
		i -= 1
	mf = r < 0
	for _ in range(k // 2):
		t = a[i] * a[i - 1]
		u = a[j] * a[j + 1]
		if not mf and t >= u or (mf and t < u):
			r *= t
			r %= mod
			i -= 2
		else:
			r *= u
			r %= mod
			j += 2
	return r
print(main())


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(list(map(int, input().split())))
pi = 1
ni = 0
ans = 1
i = 0
while i < k - 1:
	if a[ni] * a[ni + 1] > a[-pi] * a[-pi - 1]:
		ans = ans * a[ni] * a[ni + 1] % mod
		ni += 2
		i += 2
	else:
		ans = ans * a[-pi] % mod
		pi += 1
		i += 1
if i == k - 1:
	ans = ans * a[-pi] % mod
if a[-1] < 0 and k % 2 == 1:
	ans = 1
	for i in a[n - k:]:
		ans = ans * i % mod
print(ans)


(N, K) = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 10 ** 9 + 7
P = []
M = []
z = 0
for a in A:
	if a > 0:
		P.append(a)
	elif a < 0:
		M.append(a)
	else:
		z += 1
P.sort()
M.sort()
ans = 1
if len(M) == 0 or N == K:
	A.sort(reverse=True)
	for i in range(K):
		ans *= A[i]
		ans %= mod
elif len(P) == 0:
	if K % 2 == 0 and len(M) >= K:
		for i in range(K):
			ans *= M[i]
			ans %= mod
	elif K % 2 == 1 and z == 0:
		for i in range(-1, -K - 1, -1):
			ans *= M[i]
			ans %= mod
	else:
		ans = 0
elif N - z < K or (N - z == K and len(M) % 2 == 1):
	ans = 0
else:
	L = []
	for i in range(N):
		if A[i] == 0:
			continue
		L.append((abs(A[i]), A[i]))
	L.sort(reverse=True)
	cnt = 0
	lp = -1
	lm = -1
	for i in range(K):
		if L[i][1] > 0:
			lp = i
		else:
			lm = i
			cnt += 1
		ans *= L[i][0]
		ans %= mod
	if cnt % 2 == 1:
		p = -1
		m = -1
		for i in range(K, len(L)):
			if p > 0 and m > 0:
				break
			if L[i][1] > 0 and p < 0:
				p = L[i][0]
			elif L[i][1] < 0 and m < 0:
				m = L[i][0]
		if p < 0:
			ans *= m * pow(L[lp][0], mod - 2, mod)
		elif m < 0:
			ans *= p * pow(L[lm][0], mod - 2, mod)
		elif lp >= 0 and L[lm][0] * m > L[lp][0] * p:
			ans *= m * pow(L[lp][0], mod - 2, mod)
		else:
			ans *= p * pow(L[lm][0], mod - 2, mod)
		ans %= mod
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A_neg = []
A_pos = []
for i in range(N):
	if A[i] <= 0:
		A_neg.append(-A[i])
	else:
		A_pos.append(A[i])
A_neg.sort(reverse=True)
A_pos.sort(reverse=True)
ans = 1
if K == N:
	for i in range(N):
		ans *= A[i] % 1000000007
		ans %= 1000000007
	print(ans)
elif K % 2 == 1 and len(A_pos) == 0:
	for i in range(1, K + 1):
		ans *= -A_neg[-i] % 1000000007
		ans %= 1000000007
	print(ans)
else:
	if K % 2 == 1:
		ans *= A_pos.pop(0)
		K -= 1
	buf = []
	for i in range(len(A_pos) // 2):
		buf.append(A_pos[2 * i] * A_pos[2 * i + 1])
	for i in range(len(A_neg) // 2):
		buf.append(A_neg[2 * i] * A_neg[2 * i + 1])
	buf.sort(reverse=True)
	for i in range(K // 2):
		ans *= buf[i] % 1000000007
		ans %= 1000000007
	print(ans)


from functools import reduce
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
if n == k:
	print(reduce(lambda ac, v: ac * v % mod, a, 1))
	exit()
a.sort(key=lambda v: abs(v), reverse=True)
if len(list(filter(lambda v: v < 0, a))) == n and k % 2 == 1:
	print(reduce(lambda ac, v: ac * v % mod, a[n - k:], 1))
	exit()
ans = 1
mn = 0
for v in a[:k]:
	if v < 0:
		mn += 1
	ans *= abs(v)
	ans %= mod
if mn % 2 == 0:
	print(ans)
	exit()
(mnp, mnn) = (0, 0)
for v in a[k - 1::-1]:
	if mnp != 0 and mnn != 0:
		break
	elif mnp == 0 and v > 0:
		mnp = v
	elif mnn == 0 and v < 0:
		mnn = v
(mxp, mxn) = (0, 0)
for v in a[k:]:
	if mxp != 0 and mxn != 0:
		break
	elif mxp == 0 and v > 0:
		mxp = v
	elif mxn == 0 and v < 0:
		mxn = v
(x, y) = (mxp, mnn)
if mnp != 0 and mxn * mnn > mxp * mnp:
	(x, y) = (mxn, mnp)
ans *= pow(abs(y), mod - 2, mod)
ans %= mod
ans *= abs(x)
ans %= mod
print(ans)


import sys
sys.setrecursionlimit(500005)
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().strip()
(n, k) = na()
a = na()
neg = []
pos = []
for i in range(n):
	if a[i] < 0:
		neg.append(a[i])
	elif a[i] > 0:
		pos.append(a[i])
neg.sort()
pos.sort(reverse=True)
mx = -1
arg = -1
lall = 0
(nn, np) = (0, k)
while np > len(pos):
	np -= 2
	nn += 2
if np >= 0 and nn <= len(neg):
	arg = nn
	while np - 2 >= 0 and nn + 1 < len(neg):
		if pos[np - 1] * pos[np - 2] < neg[nn] * neg[nn + 1]:
			nn += 2
			np -= 2
			arg = nn
		else:
			break
ans = 1
mod = 1000000007
if arg == -1:
	a.sort(reverse=True)
	for i in range(k):
		ans = ans * a[i] % mod
	print(ans)
else:
	for i in range(arg):
		ans = ans * neg[i] % mod
	for i in range(k - arg):
		ans = ans * pos[i] % mod
	print(ans)


from functools import reduce
mod = 10 ** 9 + 7
(N, K, *A) = map(int, open(0).read().split())
A.sort(reverse=True)
ans = 1
(l, r) = (0, N - 1)
if K % 2 == 1:
	ans = A[0]
	l = 1
if ans < 0:
	print(reduce(lambda a, b: a * b % mod, A[:K], 1))
	quit()
for i in range(K // 2):
	L = A[l] * A[l + 1]
	R = A[r] * A[r - 1]
	if L >= R:
		ans *= L
		l += 2
	else:
		ans *= R
		r -= 2
	ans %= mod
print(ans)


mod = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())))
pi = 1
ni = 0
ans = 1
i = 0
while i < K - 1:
	if A[ni] * A[ni + 1] > A[-pi] * A[-pi - 1]:
		ans = ans * A[ni] * A[ni + 1] % mod
		ni += 2
		i += 2
	else:
		ans = ans * A[-pi] % mod
		pi += 1
		i += 1
if i == K - 1:
	ans = ans * A[-pi] % mod
if A[-1] < 0 and K % 2 == 1:
	ans = 1
	for i in A[N - K:]:
		ans = ans * i % mod
print(ans)


from collections import deque
import sys
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
M = 10 ** 9 + 7
if N == K:
	T = 1
	for a in A:
		T = T * a % M
	print(T)
	sys.exit()
elif max(A) < 0 and K % 2 == 1:
	A.sort(reverse=True)
	T = 1
	for i in range(K):
		T = T * A[i] % M
	print(T)
	sys.exit()
U = list(map(lambda x: max(x, 0), A))
U.sort(reverse=True)
U = deque(U)
V = list(map(lambda x: min(x, 0), A))
V.sort()
V = deque(V)
T = 1
Y = 0
while Y < K:
	(x1, x2) = (U[0], U[1])
	(y1, y2) = (V[0], V[1])
	if Y == K - 1 or x1 * x2 >= y1 * y2:
		Y += 1
		T = T * x1 % M
		_ = U.popleft()
		U.append(0)
	else:
		Y += 2
		T = T * y1 * y2 % M
		_ = V.popleft()
		_ = V.popleft()
		V.append(0)
		V.append(0)
print(T)


(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 10 ** 9 + 7
v = []
if k == n:
	v = a
elif k % 2 and max(a) < 0:
	v = sorted([a[i] for i in range(n) if a[i] < 0], reverse=True)[:k]
else:
	a = sorted(a, key=lambda x: abs(x), reverse=True)
	pi = ni = -1
	cnt = 0
	for i in range(k):
		v.append(a[i])
		if a[i] < 0:
			ni = i
			cnt ^= 1
		if a[i] > 0:
			pi = i
	if cnt % 2:
		mx = max(a[k:])
		mn = min(a[k:])
		if pi >= 0 and abs(a[pi] * mx) <= abs(a[ni] * mn):
			v.append(mn)
			v.remove(a[pi])
		else:
			v.append(mx)
			v.remove(a[ni])
ans = 1
for i in range(k):
	ans *= v[i]
	ans %= mod
print(ans)


from math import log10 as log2
(N, K) = map(int, input().split())
A = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
p = []
m = []
for a in A:
	if a > 0:
		p.append(a)
	elif a < 0:
		m.append(-a)
p.sort(reverse=True)
m.sort(reverse=True)
pl = [0]
ml = [0]
for i in range(len(p)):
	pl.append(log2(p[i]))
for i in range(len(m)):
	ml.append(log2(m[i]))
for i in range(1, len(pl)):
	pl[i] += pl[i - 1]
for i in range(1, len(ml)):
	ml[i] += ml[i - 1]
Mi = -1
Mv = 0
for i in range(0, len(ml), 2):
	j = K - i
	if len(pl) <= j or j < 0:
		continue
	if ml[i] + pl[j] > Mv:
		(Mi, Mv) = (i, ml[i] + pl[j])
if Mi != -1:
	ret = 1
	for i in range(K - Mi):
		ret *= p[i]
		ret %= mod
	for i in range(Mi):
		ret *= m[i]
		ret %= mod
else:
	x = [abs(a) for a in A]
	x.sort()
	ret = 1
	for i in range(K):
		ret *= x[i]
		ret %= mod
	ret = -ret % mod
print(ret)


from copy import deepcopy
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
ans = 1
(i, j) = (0, n - 1)
k2 = deepcopy(k)
while k2 > 1:
	if a[i] * a[i + 1] > a[j] * a[j - 1]:
		ans *= a[i] * a[i + 1]
		ans %= mod
		i += 2
		k2 -= 2
	else:
		ans *= a[j]
		j -= 1
		ans %= mod
		k2 -= 1
if k2 == 1:
	ans *= a[j]
	ans %= mod
if a[-1] < 0 and k % 2:
	ans = 1
	for i in range(n - k, n):
		ans *= a[i]
		ans %= mod
print(ans)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if N == 1:
		print(A[0])
		exit()
	A.sort()
	A2n = []
	for i in range(0, N, 2):
		if i + 1 >= N:
			break
		if A[i] <= 0 and A[i + 1] <= 0:
			A2n.append(A[i] * A[i + 1])
		else:
			break
	A.sort(reverse=True)
	ans = 1
	if A[0] <= 0 and K % 2 == 1:
		for i in range(K):
			ans = ans * A[i] % MOD
		print(ans)
		exit()
	ni = 0
	i = 0
	while K > 0:
		if i + 1 < N and len(A2n) - ni > 0 and (A[i] * A[i + 1] < A2n[ni]) and (K >= 2):
			ans = ans * A2n[ni] % MOD
			K -= 2
			ni += 1
		else:
			ans = ans * A[i] % MOD
			i += 1
			K -= 1
	print(ans)
main()


import sys

def main():
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A_list = list(map(int, sys.stdin.readline().split()))
	A_list.sort(key=lambda x: -abs(x))
	mod = 10 ** 9 + 7
	L_plus = R_plus = -1
	L_minus = R_minus = -1
	for i in range(K - 1, -1, -1):
		if L_plus == -1 and A_list[i] >= 0:
			L_plus = i
		if L_minus == -1 and A_list[i] < 0:
			L_minus = i
		if L_plus != -1 and L_minus != -1:
			break
	for i in range(K, N):
		if R_plus == -1 and A_list[i] >= 0:
			R_plus = i
		if R_minus == -1 and A_list[i] < 0:
			R_minus = i
		if R_plus != -1 and R_minus != -1:
			break
	cnt_minus = 0
	for i in range(K):
		if A_list[i] < 0:
			cnt_minus += 1
	if cnt_minus % 2 == 0:
		target = A_list[:K]
	else:
		if R_plus == -1 and (L_plus == -1 or R_minus == -1):
			calc1 = calc2 = 0
		elif R_plus != -1 and (L_plus == -1 or R_minus == -1):
			calc1 = 1
			calc2 = 0
		elif R_plus == -1 and (L_plus != -1 and R_minus != -1):
			calc1 = 0
			calc2 = 1
		elif R_plus != -1 and (L_plus != -1 and R_minus != -1):
			calc1 = A_list[L_plus] * A_list[R_plus]
			calc2 = A_list[L_minus] * A_list[R_minus]
		if calc1 == calc2:
			target = A_list[N - K:N]
		elif calc1 > calc2:
			(A_list[L_minus], A_list[R_plus]) = (A_list[R_plus], A_list[L_minus])
			target = A_list[:K]
		elif calc1 < calc2:
			(A_list[L_plus], A_list[R_minus]) = (A_list[R_minus], A_list[L_plus])
			target = A_list[:K]
	ans = 1
	for i in range(len(target)):
		ans *= target[i]
		ans %= mod
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list([v for v in a if v >= 0])
a_neg = list([v for v in a if v < 0])
a_pos.sort(reverse=True)
a_neg.sort()
mod = 10 ** 9 + 7
ans = 1
if n == k:
	for a_i in a:
		ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
	for i in reversed(list(range(len(a_neg) - k, len(a_neg)))):
		ans = ans * a_neg[i] % mod
else:
	i_p = 0
	i_n = 0
	i = 0
	while i < k:
		if i_p < len(a_pos) and (i == k - 1 or i_n + 1 >= len(a_neg) or a_pos[i_p] * (a_pos[i_p + 1] if i_p + 1 < len(a_pos) else 1) > a_neg[i_n] * a_neg[i_n + 1]):
			ans = ans * a_pos[i_p] % mod
			i_p += 1
			i += 1
		else:
			ans = ans * a_neg[i_n] % mod * a_neg[i_n + 1] % mod
			i_n += 2
			i += 2
print(ans)


import heapq
(N, K) = map(int, input().split())
A = list((int(a) for a in input().split()))
MOD = 10 ** 9 + 7
if N == K:
	ans = 1
	for a in A:
		ans = ans * a % MOD
else:
	pos = []
	neg = []
	for a in A:
		if a >= 0:
			pos.append(a)
		else:
			neg.append(a)
	if len(neg) == N and K & 1 == 1:
		neg.sort(reverse=True)
		ans = 1
		for i in range(K):
			ans = ans * neg[i] % MOD
	else:
		pos.sort(reverse=True)
		dbl = []
		ans = 1
		ini = 0
		rem = K
		if K & 1 == 1:
			ans = ans * pos[0] % MOD
			ini = 1
			rem -= 1
		for i in range(0, (len(pos) - ini) // 2):
			heapq.heappush(dbl, pos[ini + i * 2] * pos[ini + i * 2 + 1] * -1)
		neg.sort()
		for i in range(0, len(neg) // 2):
			heapq.heappush(dbl, neg[i * 2] * neg[i * 2 + 1] * -1)
		while rem > 0:
			ans = ans * heapq.heappop(dbl) * -1 % MOD
			rem -= 2
print(ans)


import sys

def main():
	(N, K) = list(map(int, sys.stdin.readline().split()))
	A_list = list(map(int, sys.stdin.readline().split()))
	A_list.sort(key=lambda x: -abs(x))
	A_plus = []
	A_minus = []
	mod = 10 ** 9 + 7
	for val in A_list:
		if val >= 0:
			A_plus.append(val)
		else:
			A_minus.append(val)
	if not A_plus:
		if K % 2 == 0:
			target_range = list(range(K))
		else:
			target_range = list(range(len(A_minus) - K, len(A_minus)))
		ans = 1
		for i in target_range:
			ans *= A_minus[i]
			ans %= mod
		print(ans)
		return
	if not A_minus:
		ans = 1
		for i in range(K):
			ans *= A_plus[i]
			ans %= mod
		print(ans)
		return
	select = []
	i_p = 0
	i_m = 0
	while len(select) < K:
		if K - len(select) == 1:
			if i_p < len(A_plus):
				select.append(A_plus[i_p])
				i_p += 1
				break
			else:
				ans = 1
				for i in range(len(A_list) - K, len(A_list)):
					ans *= A_list[i]
					ans %= mod
				print(ans)
				return
		if i_m + 1 < len(A_minus):
			if i_p + 1 < len(A_plus):
				if abs(A_plus[i_p] * A_plus[i_p + 1]) > abs(A_minus[i_m] * A_minus[i_m + 1]):
					select.append(A_plus[i_p])
					i_p += 1
				else:
					select.extend([A_minus[i_m], A_minus[i_m + 1]])
					i_m += 2
			else:
				select.extend([A_minus[i_m], A_minus[i_m + 1]])
				i_m += 2
		else:
			select.append(A_plus[i_p])
			i_p += 1
	ans = 1
	for i in range(K):
		ans *= select[i]
		ans %= mod
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for v in A:
	if v >= 0:
		pos.append(v)
	else:
		neg.append(-v)
pos.sort(reverse=True)
neg.sort(reverse=True)
MOD = 10 ** 9 + 7
ppos = [1] * (len(pos) + 1)
pneg = [1] * (len(neg) + 1)
for (i, v) in enumerate(pos):
	ppos[i + 1] = ppos[i] * v % MOD
for (i, v) in enumerate(neg):
	pneg[i + 1] = pneg[i] * v % MOD
i = j = 0
while i + j < K:
	if i == len(pos):
		j += 1
	elif j == len(neg) or pos[i] >= neg[j]:
		i += 1
	else:
		j += 1
if j % 2 == 1:
	v = (-1, -1, -1)
	if i and j < len(neg):
		v = (neg[j - 1] * neg[j], i - 1, j + 1)
	if i < len(pos) and j:
		v = max(v, (pos[i - 1] * pos[i], i + 1, j - 1))
	if v[0] == -1:
		X = pos + neg
		X.sort()
		r = 1
		for v in X[:K]:
			r = r * v % MOD
		print(-r % MOD)
		raise SystemExit
	(i, j) = v[1:]
r = 1
for x in pos[:i]:
	r = r * x % MOD
for x in neg[:j]:
	r = r * x % MOD
print(r)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
(b, c, d) = (0, 0, 0)
mod = 10 ** 9 + 7
B = []
C = []
D = []
for a in A:
	if a < 0:
		b += 1
		B.append(a)
	elif a == 0:
		c += 1
		C.append(a)
	else:
		d += 1
		D.append(a)
if B:
	B.sort()
if D:
	D.sort(reverse=True)
if K > b + d:
	print(0)
elif K == b + d and K < N and (b % 2 == 1):
	print(0)
elif K == N:
	ans = 1
	for i in range(N):
		ans = ans * A[i] % mod
	print(ans)
elif b == N and K % 2 == 1:
	ans = 1
	for i in range(1, K + 1):
		ans = ans * B[-i] % mod
	print(ans)
elif K < b and d == 0 and (K % 2 == 1):
	print(0)
else:
	bi = 0
	di = 0
	ans = 1
	while K > 1:
		if bi >= b - 1 or (di + 1 < d and D[di] * D[di + 1] > B[bi] * B[bi + 1]):
			ans = ans * D[di] % mod
			ans = ans * D[di + 1] % mod
			di += 2
		else:
			ans = ans * B[bi] % mod
			ans = ans * B[bi + 1] % mod
			bi += 2
		K -= 2
	if K == 1:
		ans = ans * D[di] % mod
	print(ans)


MOD = 10 ** 9 + 7

def prod(a):
	res = 1
	for x in a:
		res = res * x % MOD
	return res

def solve(n, k, a):
	if k == 1:
		return max(a)
	elif k == n:
		return prod(a)
	elif max(a) < 0 and k % 2 == 1:
		a = sorted(a, reverse=True)
		return prod(a[:k])
	else:
		a = sorted(a, key=lambda x: -abs(x))
		num_negative = len(list([x for x in a[:k] if x < 0]))
		if num_negative % 2 == 0:
			return prod(a[:k])
		else:
			(i1, j1) = (None, None)
			for i in range(k):
				if a[i] < 0:
					i1 = i
			for j in range(k, n):
				if a[j] >= 0:
					j1 = j
					break
			(i2, j2) = (None, None)
			for i in range(k):
				if a[i] >= 0:
					i2 = i
			for j in range(k, n):
				if a[j] < 0:
					j2 = j
					break
			if i1 is None or j1 is None:
				return prod(a[:i2] + a[i2 + 1:k] + [a[j2]])
			elif i2 is None or j2 is None:
				return prod(a[:i1] + a[i1 + 1:k] + [a[j1]])
			elif abs(a[j1] * a[i2]) > abs(a[i1] * a[j2]):
				return prod(a[:i1] + a[i1 + 1:k] + [a[j1]])
			else:
				return prod(a[:i2] + a[i2 + 1:k] + [a[j2]])
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
print(solve(n, k, a))


from math import log
mod = int(1000000000.0) + 7
(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

def sign(v):
	if v == 0:
		return 0
	return 1 if v > 0 else -1
pref = [(0, 1)] * (n + 1)
suf = [(0, 1)] * (n + 1)
c = 1
sm = 0
sgn = 1
for j in range(n):
	c = c * a[j] % mod
	sgn *= sign(a[j])
	if a[j] != 0:
		sm += log(abs(a[j]))
	pref[j + 1] = (sgn * sm, c, sgn)
c = 1
sm = 0
sgn = 1
for j in range(n):
	c = c * a[n - j - 1] % mod
	sgn *= sign(a[n - j - 1])
	if a[n - j - 1] != 0:
		sm += log(abs(a[n - j - 1]))
	suf[j + 1] = (sgn * sm, c, sgn)
m = max(pref[k], suf[k])
for i in range(1, k):
	sgn = pref[i][2] * suf[k - i][2]
	pm = pref[i][1] * suf[k - i][1] % mod
	sm = abs(pref[i][0]) + abs(suf[k - i][0])
	m = max(m, (sgn * sm, pm, sgn))
print(m[1])


(N, K) = map(int, input().split())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7
if K % 2 == 1 and all((v < 0 for v in X)):
	X.sort(key=lambda x: -x)
	ans = 1
	for i in range(K):
		ans = ans * X[i] % MOD
	print(ans)
elif K == N:
	ans = 1
	for i in range(K):
		ans = ans * X[i] % MOD
	print(ans)
else:
	pos = sorted((v for v in X if v >= 0))
	neg = sorted((-v for v in X if v < 0))
	ans = 1
	if K % 2 == 1:
		ans *= pos.pop()
	cand = []
	while len(pos) >= 2:
		tmp = pos.pop() * pos.pop()
		cand.append(tmp)
	while len(neg) >= 2:
		tmp = neg.pop() * neg.pop()
		cand.append(tmp)
	cand.sort(reverse=True)
	for i in range(K // 2):
		ans = ans * cand[i] % MOD
	print(ans)


import sys
mod = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
if A[0] < 0 and K % 2 == 1:
	ans = 1
	for i in range(K):
		ans *= A[i]
		ans %= mod
	print(ans)
	sys.exit()
l = 0
r = N - 1
ans = 1
if K % 2 == 1:
	ans *= A[0]
	l += 1
for _ in range(K // 2):
	if A[l] * A[l + 1] > A[r] * A[r - 1]:
		ans *= A[l] * A[l + 1]
		ans %= mod
		l += 2
	else:
		ans *= A[r] * A[r - 1]
		ans %= mod
		r -= 2
print(ans)


def solve(n, k, a):
	mod = 10 ** 9 + 7
	ans = 1
	l = 0
	r = n - 1
	a.sort()
	if k % 2 == 1:
		ans *= a[r]
		r -= 1
	if ans < 0:
		ans = 1
		for i in range(k):
			ans *= a[n - i - 1]
			ans %= mod
		return ans
	for i in range(k // 2):
		tmp_min = a[l] * a[l + 1]
		tmp_max = a[r] * a[r - 1]
		if tmp_max > tmp_min:
			ans *= tmp_max
			ans %= mod
			r -= 2
		else:
			ans *= tmp_min
			ans %= mod
			l += 2
	return ans
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
ans = solve(n, k, A)
print(ans)


import operator
from functools import reduce
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
positives = [a for a in A if a > 0]
negatives = [a for a in A if a < 0]
positive_cnt = len(positives)
negative_cnt = len(negatives)
zero_cnt = A.count(0)
if 2 * min(K // 2, negative_cnt // 2) + positive_cnt >= K:
	ans = 1
	positives.sort(key=lambda x: abs(x), reverse=True)
	negatives.sort(key=lambda x: abs(x), reverse=True)
	if K % 2 == 1:
		ans *= positives.pop(0)
		K -= 1
	X = []
	for pair in zip(*[iter(positives)] * 2):
		X.append(reduce(operator.mul, pair, 1))
	for pair in zip(*[iter(negatives)] * 2):
		X.append(reduce(operator.mul, pair, 1))
	X.sort(reverse=True)
	ans *= reduce(lambda a, b: a * b % MOD, X[:K // 2], 1)
	print(ans % MOD)
elif zero_cnt:
	print(0)
else:
	A.sort(key=lambda x: abs(x))
	print(reduce(lambda a, b: a * b % MOD, A[:K], 1) % MOD)


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

def solve():
	A.sort(key=lambda x: abs(x), reverse=True)
	ans = 1
	nneg = 0
	(a, b, c, d) = (-1, -1, -1, -1)
	for k in range(K):
		ans = ans * A[k] % MOD
		if A[k] < 0:
			nneg += 1
			b = k
		else:
			a = k
	if K == N or nneg % 2 == 0:
		return ans
	for k in range(N - 1, K - 1, -1):
		if A[k] < 0:
			d = k
		else:
			c = k
	if a == -1 and c == -1:
		ans = 1
		for k in range(K):
			ans = ans * A[-1 - k] % MOD
		return ans
	if a == -1 or d == -1:
		outn = A[b]
		inn = A[c]
	elif c == -1:
		outn = A[a]
		inn = A[d]
	elif A[a] * A[c] > A[b] * A[d]:
		outn = A[b]
		inn = A[c]
	else:
		outn = A[a]
		inn = A[d]
	ans = ans * pow(outn, MOD - 2, MOD) % MOD
	ans = ans * inn % MOD
	return ans

def __starting_point():
	print(solve())
__starting_point()


MOD = 10 ** 9 + 7
(n, k) = list(map(int, input().split()))
alst = list(map(int, input().split()))
alst.sort()
if n == k:
	ans = 1
	for num in alst:
		ans *= num
		ans %= MOD
	print(ans)
	return
if k == 1:
	print(alst[-1] % MOD)
	return
if alst[0] >= 0:
	ans = 1
	alst.sort(reverse=True)
	for i in range(k):
		ans *= alst[i]
		ans %= MOD
	print(ans)
	return
if alst[-1] <= 0:
	ans = 1
	if k % 2 == 1:
		alst = alst[::-1]
	for i in range(k):
		ans *= alst[i]
		ans %= MOD
	print(ans)
	return
blst = []
for num in alst:
	try:
		blst.append([abs(num), abs(num) // num])
	except ZeroDivisionError:
		blst.append([abs(num), 0])
blst.sort(reverse=True, key=lambda x: x[0])
if blst[k - 1] == 0:
	print(0)
	return
minus = 0
last_minus = 0
last_plus = 0
ans_lst = []
for i in range(k):
	if blst[i][1] == -1:
		minus += 1
		last_minus = blst[i][0]
	elif blst[i][1] == 1:
		last_plus = blst[i][0]
	else:
		print(0)
		return
	ans_lst.append(blst[i][0])
next_minus = 0
next_plus = 0
flg_minus = False
flg_plus = False
for i in range(k, n):
	if blst[i][1] == -1 and (not flg_minus):
		next_minus = blst[i][0]
		flg_minus = True
	if blst[i][1] == 1 and (not flg_plus):
		next_plus = blst[i][0]
		flg_plus = True
	if flg_plus and flg_minus or blst[i][1] == 0:
		break
if minus % 2 == 0:
	ans = 1
	for num in ans_lst:
		ans *= num
		ans %= MOD
	print(ans)
else:
	minus_s = last_minus * next_minus
	plus_s = last_plus * next_plus
	ans = 1
	if minus == k:
		ans_lst.remove(last_minus)
		ans_lst.append(next_plus)
	elif minus_s == plus_s == 0:
		if next_minus == 0:
			ans_lst.remove(last_minus)
			ans_lst.append(next_plus)
		else:
			print(0)
			return
	elif minus_s > plus_s:
		ans_lst.remove(last_plus)
		ans_lst.append(next_minus)
	else:
		ans_lst.remove(last_minus)
		ans_lst.append(next_plus)
	for num in ans_lst:
		ans *= num
		ans %= MOD
	print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
a.sort()
if n == k:
	ans = 1
	for num in a:
		ans *= num
		ans %= mod
	print(ans)
	exit()
if a[-1] < 0:
	if k % 2 == 1:
		a.sort(reverse=True)
		ans = 1
		for num in a[:k]:
			ans *= num
			ans %= mod
		print(ans)
		exit()
ans = 1
if k % 2 == 1:
	ans = a[-1]
	a.pop(-1)
	k -= 1
pz_a = []
m_a = []
for num in a:
	if num < 0:
		m_a.append(num)
	else:
		pz_a.append(num)
pz_a.sort(reverse=True)
c2_a = []
lastnum = -1
for i in range(len(pz_a)):
	num1 = pz_a[i]
	if lastnum == -1:
		lastnum = num1
	else:
		c2_a.append(lastnum * num1)
		lastnum = -1
lastnum = 1
for i in range(len(m_a)):
	num1 = m_a[i]
	if lastnum == 1:
		lastnum = num1
	else:
		c2_a.append(lastnum * num1)
		lastnum = 1
c2_a.sort(reverse=True)
for num in c2_a[:k // 2]:
	ans *= num
	ans %= mod
print(ans)


import sys
(n, k) = list(map(int, input().split()))
a = [int(x) for x in input().split()]
mod = pow(10, 9) + 7
zero = 0
plus = []
minus = []
for i in range(n):
	if a[i] == 0:
		zero += 1
	elif a[i] > 0:
		plus.append(a[i])
	else:
		minus.append(a[i])
(P, M) = (len(plus), len(minus))
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
	for i in range(n):
		ans *= a[i]
		ans %= mod
elif P + M < k:
	ans = 0
elif P == 0 and k % 2 == 1:
	if zero >= 1:
		ans = 0
	else:
		minus.sort(reverse=True)
		for i in range(k):
			ans *= minus[i]
			ans %= mod
else:
	q = 0
	if k % 2 == 1:
		ans *= plus[0]
		ans %= mod
		q = 1
	judge = []
	for i in range((len(plus) - q) // 2):
		judge.append(plus[2 * i + q] * plus[2 * i + q + 1])
	for i in range(len(minus) // 2):
		judge.append(minus[2 * i] * minus[2 * i + 1])
	judge.sort(reverse=True)
	for i in range(k // 2):
		ans *= judge[i] % mod
		ans %= mod
print(ans)


mod = 1000000007
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
ans = 1
if len(A) == K:
	for i in range(K):
		ans = ans * (A[i] % mod) % mod
elif A[-1] < 0 and K % 2 == 1:
	for i in range(K):
		ans = ans * (A[-i - 1] % mod) % mod
else:
	n = 0
	p = -1
	if K % 2 == 1:
		ans = ans * (A[p] % mod) % mod
		p -= 1
	for _ in range(K // 2):
		if A[n] * A[n + 1] > A[p] * A[p - 1]:
			ans = ans * (A[n] % mod) % mod
			ans = ans * (A[n + 1] % mod) % mod
			n += 2
		else:
			ans = ans * (A[p] % mod) % mod
			ans = ans * (A[p - 1] % mod) % mod
			p -= 2
print(ans)


(N, K) = map(int, input().split())
A = [int(a) for a in input().split()]
(Ap, Am, A0) = ([], [], [])
for a in A:
	if a > 0:
		Ap.append(a)
	elif a < 0:
		Am.append(a)
	else:
		A0.append(a)
mod = 10 ** 9 + 7
ans = 1
if N == K:
	for a in A:
		ans = ans * a % mod
	print(ans)
	exit()
if len(Ap) == 0 and K % 2 == 1:
	if len(A0) == 0:
		A.sort()
		A.reverse()
		for i in range(K):
			ans = ans * A[i] % mod
		print(ans)
		exit()
	else:
		print(0)
		exit()
Ap.sort()
Ap.reverse()
Am.sort()
if K % 2 == 1:
	ans = Ap[0]
	Ap = Ap[1:]
	K -= 1
if K > len(Ap) + len(Am):
	print(0)
	exit()
if K == len(Ap) + len(Am) and len(Am) % 2 == 1:
	print(0)
	exit()
Apair = [Ap[i] * Ap[i + 1] for i in range(0, len(Ap) - 1, 2)]
for i in range(0, len(Am) - 1, 2):
	Apair.append(Am[i] * Am[i + 1])
Apair.sort()
Apair.reverse()
for i in range(K // 2):
	ans = ans * Apair[i] % mod
print(ans)


import math
import sys
(N, K) = map(int, input().split())
A = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7

def modinv(a):
	b = MOD
	u = 1
	v = 0
	while b != 0:
		t = a // b
		a -= t * b
		(a, b) = (b, a)
		u -= t * v
		(u, v) = (v, u)
	u %= MOD
	if u < 0:
		u += MOD
	return u

def solve(N, K, A):
	A = sorted(A, key=lambda x: abs(x))
	if A[N - K] == 0:
		return 0
	(Lpos0, Lneg0, Rpos0, Rneg0) = (None, None, None, None)
	(Lneg, Lpos, Rneg, Rpos) = (0, 0, 0, 0)
	answer0 = 1
	for i in range(N - K, N):
		if A[i] < 0:
			if Rneg == 0:
				Rneg0 = -A[i]
			Rneg += 1
		else:
			if Rpos == 0:
				Rpos0 = A[i]
			Rpos += 1
		answer0 = answer0 * abs(A[i]) % MOD
	if Rneg % 2 == 0:
		return answer0
	for i in range(N - K)[::-1]:
		if A[i] < 0:
			if Lneg == 0:
				Lneg0 = -A[i]
			Lneg += 1
		else:
			if Lpos == 0:
				Lpos0 = A[i]
			Lpos += 1
	print(f'K={K!r}', file=sys.stderr)
	if Lpos0 is not None and Rneg0 is not None and (Rpos0 is not None) and (Lneg0 is not None):
		answer1 = answer0 * modinv(Rneg0) % MOD * Lpos0 % MOD
		answer2 = answer0 * modinv(Rpos0) % MOD * Lneg0 % MOD
		print(f'Lpos0={Lpos0!r}, Lneg0={Lneg0!r}, Rpos0={Rpos0!r} Rneg0={Rneg0!r}', file=sys.stderr)
		print(f'answer1={answer1!r} answer2={answer2!r}', file=sys.stderr)
		print(f'A Lpos0*Lneg0={Lpos0 * Lneg0!r} Rneg0*Rpos0={Rneg0 * Rpos0!r}', file=sys.stderr)
		if Lpos0 * Rpos0 > Lneg0 * Rneg0:
			print(f'A1 answer1={answer1!r}', file=sys.stderr)
			return answer1
		else:
			print(f'A2 answer2={answer2!r}', file=sys.stderr)
			return answer2
	if Lpos0 is not None and Rneg0 is not None:
		print('B', file=sys.stderr)
		return answer0 * modinv(Rneg0) % MOD * Lpos0 % MOD
	if Rpos0 is not None and Lneg0 is not None:
		print('C', file=sys.stderr)
		return answer0 * modinv(Rpos0) % MOD * Lneg0 % MOD
	print('D', file=sys.stderr)
	answer0 = 1
	for i in range(K):
		answer0 = answer0 * A[i] % MOD
	return answer0
print(solve(N, K, A))


def main(A, n, k):
	MOD = int(1000000000.0) + 7
	A.sort()
	ans = 1
	if A[n - 1] == 0 and k & 1:
		ans = 0
	elif A[n - 1] <= 0 and k & 1:
		for i in range(n - 1, n - k - 1, -1):
			ans = ans * A[i] % MOD
	else:
		i = 0
		j = n - 1
		if k & 1:
			ans = ans * A[j] % MOD
			j -= 1
			k -= 1
		k >>= 1
		for itr in range(k):
			left_product = A[i] * A[i + 1]
			right_product = A[j] * A[j - 1]
			if left_product > right_product:
				ans = ans * left_product % MOD
				i += 2
			else:
				ans = ans * right_product % MOD
				j -= 2
	print(ans % MOD)
(N, K) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
main(A, N, K)


(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 1000000007
arr = []
j = 0
i = 0
seki = 1
gyaku = 1
minuscount = 0
minusposition = 0

def modpow(a, n, mod):
	res = 1
	while n > 0:
		if n & 1:
			res = res * a % mod
		a = a * a % mod
		n >>= 1
	return res

def modinv(a, mod):
	return modpow(a, mod - 2, mod)
arr = sorted(A, reverse=True)
if arr[N - 1] > 0:
	for i in range(K):
		seki = seki * arr[i] % MOD
elif arr[0] < 0:
	for j in range(K):
		if K % 2 == 1:
			seki = seki * arr[j] % MOD
		else:
			seki = seki * arr[N - j - 1] % MOD
else:
	while i + j < K:
		if i + j + 1 < K:
			if arr[i] * arr[i + 1] > arr[N - j - 1] * arr[N - j - 2]:
				seki = seki * arr[i] % MOD
				i += 1
			else:
				minuscount += 2
				minusposition = N - j - 2
				seki = seki * arr[N - j - 1] % MOD * arr[N - j - 2] % MOD
				j += 2
		elif abs(arr[i]) > abs(arr[N - j - 1]):
			seki = seki * arr[i] % MOD
			i += 1
		else:
			minuscount += 1
			minusposition = N - j - 1
			seki = seki * arr[N - j - 1] % MOD
			j += 1
if minuscount % 2 != 0:
	if minusposition != i - 1:
		gyaku = modinv(arr[minusposition], MOD)
		seki = seki * gyaku % MOD
		seki = seki * arr[i] % MOD
print(seki)


def abc173_e():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	A.sort(reverse=True)
	B = sorted(A, key=lambda x: abs(x), reverse=True)
	C = []
	if k == n:
		C = A
	elif k % 2 == 1 and A[0] < 0:
		C = A[:k]
	else:
		plus = []
		minus = []
		for b in B[:k]:
			if b >= 0:
				plus.append(b)
			else:
				minus.append(b)
		if len(minus) % 2 == 1:
			(rem1, add1, rem2, add2) = (None, None, None, None)
			rem1 = minus[-1]
			add1 = max(B[k:])
			valid1 = add1 >= 0
			valid2 = False
			if plus:
				rem2 = plus[-1]
				add2 = min(B[k:])
				valid2 = add2 < 0
			if valid1 and valid2:
				if add1 * rem2 > rem1 * add2:
					minus[-1] = add1
				else:
					plus[-1] = add2
			elif valid1:
				minus[-1] = add1
			elif valid2:
				plus[-1] = add2
		C = plus + minus
	ans = 1
	for c in C:
		ans *= c
		if ans < 0:
			ans += mod
		ans %= mod
	print(ans)

def __starting_point():
	abc173_e()
__starting_point()


import bisect
(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7
(n0, n1) = (bisect.bisect_left(A, 0), bisect.bisect_left(A, 1))
if N - (n1 - n0) < K:
	print(0)
	exit()
(m, z, p) = (n0, n1 - n0, N - n1)
if K - p == min(K, m) and (K - p) % 2 == 1:
	ans = 1
	for a in sorted([abs(x) for x in A])[:K]:
		ans = ans * a % MOD
	print(-ans % MOD)
else:
	if K % 2 != 0:
		(ans, i, j) = (A[-1], N - 2, 0)
	else:
		(ans, i, j) = (1, N - 1, 0)
	for _ in range(K // 2):
		if i <= n1:
			pos = False
		elif j >= n0 - 1:
			pos = True
		elif A[i] * A[i - 1] > A[j] * A[j + 1]:
			pos = True
		else:
			pos = False
		if pos:
			ans = ans * (A[i] * A[i - 1] % MOD) % MOD
			i -= 2
		else:
			ans = ans * (A[j] * A[j + 1] % MOD) % MOD
			j += 2
	print(ans)


M = 10 ** 9 + 7
(n, k, *l) = map(int, open(0).read().split())
(lp, lm) = ([], [])
for i in l:
	if i < 0:
		lm += [i]
	else:
		lp += [i]
(cp, cm) = (len(lp), len(lm))
ok = 0
if cp:
	if n == k:
		ok = 1 - cm % 2
	else:
		ok = 1
else:
	ok = 1 - k % 2
a = 1
if ok < 1:
	l.sort(key=lambda x: abs(x))
	for i in range(k):
		a = a * l[i] % M
else:
	lp.sort()
	lm.sort(reverse=1)
	if k % 2:
		a = lp.pop()
	p = []
	while len(lp) > 1:
		p += [lp.pop() * lp.pop()]
	while len(lm) > 1:
		p += [lm.pop() * lm.pop()]
	p.sort(reverse=1)
	for i in range(k // 2):
		a = a * p[i] % M
print(a)


MOD = 10 ** 9 + 7
ans = 1
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if n == k:
	for x in a:
		ans *= x
		ans %= MOD
	print(ans % MOD)
	exit()
pos = []
neg = []
for x in a:
	if x >= 0:
		pos.append(x)
	else:
		neg.append(x)
pos.sort(reverse=True)
neg.sort()
if len(pos) == 0 and k % 2:
	for i in range(1, k + 1):
		ans *= neg[-i]
		ans %= MOD
	print(ans % MOD)
	exit()
if k % 2:
	ans *= pos.pop(0)
	k -= 1
l = []
for i in range(1, len(pos), 2):
	l.append(pos[i] * pos[i - 1])
for i in range(1, len(neg), 2):
	l.append(neg[i] * neg[i - 1])
l.sort(reverse=True)
for i in range(k // 2):
	ans *= l[i]
	ans %= MOD
print(ans % MOD)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
n = len(arr)
l = 0
r = n - 1
ans = 1
if k % 2 == 1:
	ans = arr[0]
	l = 1
m = 10 ** 9 + 7
if ans < 0:
	ans = 1
	for i in range(k):
		ans *= arr[i]
		ans %= m
	print(ans)
	quit()
for i in range(k // 2):
	po = arr[l] * arr[l + 1]
	ne = arr[r] * arr[r - 1]
	if po >= ne:
		l += 2
		ans *= po
		ans %= m
	else:
		r -= 2
		ans *= ne
		ans %= m
print(ans)


(N, K) = map(int, input().split())
As = list(map(int, input().split()))
P = 10 ** 9 + 7
As.sort()
dic = {-1: 0, 1: 0}
for a in As:
	if a < 0:
		dic[-1] += 1
	else:
		dic[1] += 1
rlt = 1
j = 0
if N == K:
	for a in As:
		rlt *= a
		rlt %= P
	while rlt < 0:
		rlt += P
elif As[N - 1] < 0 and K % 2 == 1:
	for i in range(1, K + 1):
		rlt *= As[-i]
		rlt %= P
	while rlt < 0:
		rlt += P
else:
	s = 0
	i = 0
	j = 1
	while s < K:
		if i + 1 >= dic[-1] or s + 1 == K:
			rlt *= As[-j]
			rlt %= P
			j += 1
			s += 1
		elif j + 1 > dic[1]:
			rlt *= As[i] * As[i + 1]
			rlt %= P
			i += 2
			s += 2
		elif As[i] * As[i + 1] > As[-j] * As[-(j + 1)]:
			rlt *= As[i] * As[i + 1]
			rlt %= P
			i += 2
			s += 2
		else:
			rlt *= As[-j]
			rlt %= P
			j += 1
			s += 1
print(rlt)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
ans = 1
i = 0
j = -1
k_1 = k
while k_1 > 1:
	if a[i] * a[i + 1] > a[j] * a[j - 1]:
		ans = ans * a[i] * a[i + 1] % mod
		i += 2
		k_1 -= 2
	else:
		ans = ans * a[j] % mod
		j -= 1
		k_1 -= 1
if k_1 == 1:
	ans = ans * a[j] % mod
if a[-1] < 0 and k % 2 == 1:
	ans = 1
	for i in a[n - k:]:
		ans = ans * i % mod
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
(ans, num) = (1, [])
if len(pla) == 0 and k % 2 == 1:
	for i in mia[:k]:
		ans = ans * i % mod
	print(ans)
	exit()
for _ in range(k):
	if len(mia) == 0 or (len(pla) > 0 and abs(mia[-1]) <= pla[-1]):
		tmp = pla.pop()
	elif len(pla) == 0 or (len(mia) > 0 and abs(mia[-1]) > pla[-1]):
		tmp = mia.pop()
	num.append(tmp)
	ans = ans * tmp % mod
cnt = sum((i < 0 for i in num))
if cnt % 2 == 1:
	(p, q, r, s) = (1, 0, -1, 0)
	if len(mia) > 0 and cnt != k:
		(p, q) = (min((i for i in num if i >= 0)), mia[-1])
	if len(pla) > 0:
		(r, s) = (max((i for i in num if i < 0)), pla[-1])
	if len(mia) > 0 or (len(pla) > 0 and cnt != k):
		if q * r >= p * s:
			ans *= q * pow(p, mod - 2, mod)
		if q * r < p * s:
			ans *= s * pow(r, mod - 2, mod)
	ans %= mod
print(ans)


INF = 10 ** 9 + 7
(N, K) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if K == 1:
	print(a[0])
	exit()
if K == N:
	ans = 1
	for i in a:
		ans *= i
		ans %= INF
	print(ans)
	exit()
if a[0] < 0:
	ans = 1
	if K % 2 == 1:
		for i in range(K):
			ans *= a[i]
			ans %= INF
	else:
		for i in range(K):
			ans *= a[-i - 1]
			ans %= INF
	print(ans)
	exit()
sei = []
hu = []
for i in a:
	if i >= 0:
		sei.append(i)
	else:
		hu.append(i)
hu.sort()
seis = []
hus = []
total = []
ans = 1
if K % 2 != 0:
	ans = sei[0] % INF
	for i in range(2, len(sei), 2):
		seis.append(sei[i] * sei[i - 1])
else:
	for i in range(1, len(sei), 2):
		seis.append(sei[i] * sei[i - 1])
for i in range(1, len(hu), 2):
	hus.append(hu[i] * hu[i - 1])
total = hus + seis
total.sort(reverse=True)
for i in range(K // 2):
	ans *= total[i]
	ans %= INF
print(ans)


(n, k) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
mod = 10 ** 9 + 7
if A[-1] < 0 and k % 2 == 1:
	now = 1
	for i in range(k):
		now = now * A[-i - 1] % mod
	print(now)
	return
l = 0
r = n - 1
ans = 1
if k % 2 == 1:
	ans = A[-1]
	r -= 1
for i in range(k // 2):
	mi = A[l] * A[l + 1]
	pl = A[r] * A[r - 1]
	if mi > pl:
		ans = ans * mi % mod
		l += 2
	else:
		ans = ans * pl % mod
		r -= 2
print(ans % mod)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
A.sort()
ans = 1
if A[-1] == 0 and K & 1:
	print(0)
	exit()
if A[-1] < 0 and K & 1:
	for i in range(N - 1, N - 1 - K, -1):
		ans = ans * A[i] % mod
	print(ans)
	exit()
(l, r) = (0, N - 1)
if K & 1:
	ans *= A[-1]
	r -= 1
	K -= 1
p = K // 2
for i in range(p):
	lp = A[l] * A[l + 1]
	rp = A[r] * A[r - 1]
	if lp > rp:
		ans = ans * lp % mod
		l += 2
	else:
		ans = ans * rp % mod
		r -= 2
print(ans % mod)


from bisect import bisect
(N, K) = map(int, input().split())
Ali = list(map(int, input().split()))
ans = 1
Ali.sort()
mod = 10 ** 9 + 7
if K % 2 == 1:
	ans = Ali.pop()
	K -= 1
Am = Ali[0:bisect(Ali, 0)]
Ap = Ali[bisect(Ali, 0):]
if ans >= 0:
	Am.sort(reverse=True)
	Ap.sort()
else:
	Am.sort()
	Ap.sort(reverse=True)
mp = len(Am) - 1
pp = len(Ap) - 1
while K > 0:
	mmax = -1
	pmax = -1
	if mp >= 1:
		mmax = Am[mp] * Am[mp - 1]
	if pp >= 1:
		pmax = Ap[pp] * Ap[pp - 1]
	if mmax == pmax == -1:
		ans *= Am[0] * Ap[0]
		print(ans % mod)
		exit()
	if mmax >= pmax:
		ans = ans * mmax % mod
		mp -= 2
		K -= 2
	else:
		ans = ans * pmax % mod
		pp -= 2
		K -= 2
print(ans % mod)


import sys
input = sys.stdin.readline
(N, K) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
s = []
t = []
for a in A:
	if a < 0:
		t.append(a)
	else:
		s.append(a)
P = 10 ** 9 + 7
S = len(s)
T = len(t)
ok = False
if S > 0:
	if N == K:
		ok = T % 2 == 0
	else:
		ok = True
else:
	ok = K % 2 == 0
ans = 1
if not ok:
	A.sort(key=lambda x: abs(x))
	for i in range(K):
		ans = ans * A[i] % P
else:
	s.sort()
	t.sort(reverse=True)
	if K % 2 == 1:
		ans *= s.pop()
	p = []
	while len(s) >= 2:
		x = s.pop()
		x = x * s.pop()
		p.append(x)
	while len(t) >= 2:
		x = t.pop()
		x = x * t.pop()
		p.append(x)
	p.sort(reverse=True)
	for i in range(K // 2):
		ans = ans * p[i] % P
print(ans % P)


from functools import reduce
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
Ap = [a for a in A if a > 0]
Am = [a for a in A if a < 0]
mod = 10 ** 9 + 7
if len(Ap) + len(Am) < K:
	print(0)
	return
if len(Ap) + len(Am) == K:
	if 0 in A and len(Am) % 2:
		print(0)
	else:
		ans = reduce(lambda a, b: a * b % mod, Ap + Am, 1)
		print(ans)
	return
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0:
	if K % 2:
		if 0 in A:
			ans = 0
		else:
			ans = reduce(lambda a, b: a * b % mod, Am[-K:], 1)
	else:
		ans = reduce(lambda a, b: a * b % mod, Am[:K], 1)
	print(ans)
	return
idx_Am = 0
n = 0
ans = 1
for (idx_Ap, ap) in enumerate(Ap + [0]):
	while idx_Am < len(Am) and n < K and (-Am[idx_Am] > ap):
		ans = ans * Am[idx_Am] % mod
		idx_Am += 1
		n += 1
	if n == K:
		break
	n += 1
	idx_Ap += 1
	ans = ans * ap % mod
	if n == K:
		break
else:
	assert False
if idx_Am % 2 == 0:
	print(ans)
else:
	if idx_Ap == len(Ap) or (idx_Am != len(Am) and idx_Ap > 0 and (Am[idx_Am] * Am[idx_Am - 1] > Ap[idx_Ap] * Ap[idx_Ap - 1])):
		ans = ans * Am[idx_Am] * pow(Ap[idx_Ap - 1], mod - 2, mod) % mod
	else:
		ans = ans * Ap[idx_Ap] * pow(Am[idx_Am - 1], mod - 2, mod) % mod
	print(ans)


import copy
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = sorted([(a, abs(a)) for a in A], key=lambda x: x[1], reverse=True)
R = 10 ** 9 + 7
P = 1
minus = 0
last_neg = -1
last_pos = -1
for i in range(K):
	if B[i][0] > 0:
		if last_pos != -1:
			P = P * B[last_pos][1] % R
		last_pos = i
	elif B[i][0] < 0:
		if last_neg != -1:
			P = P * B[last_neg][1] % R
		minus += 1
		last_neg = i
	else:
		print(0)
		return
F = copy.copy(P)
if last_pos != -1:
	F = F * B[last_pos][1] % R
if last_neg != -1:
	F = F * B[last_neg][1] % R
if minus % 2 == 1:
	if K == N:
		print(-F % R)
		return
	first_neg = -1
	first_pos = -1
	count = [0, 0]
	for i in range(K, N):
		if count[0] == 0 and B[i][0] > 0:
			first_pos = i
			count[0] = 1
		elif count[1] == 0 and B[i][0] < 0:
			first_neg = i
			count[1] = 1
		elif count == [1, 1]:
			break
	if first_pos == -1 and last_pos == -1:
		P = 1
		for i in range(K):
			P = P * B[N - i - 1][0] % R
		print(P)
		return
	if first_pos == -1 and first_neg == -1:
		print(0)
		return
	list_product = []
	if first_neg != -1 and last_pos != -1:
		list_product.append(B[last_neg][1] * B[first_neg][1])
	if first_pos != -1:
		P1 = B[first_pos][1]
		if last_pos != -1:
			P1 = P1 * B[last_pos][1]
		list_product.append(P1)
	print(max(list_product) * P % R)
else:
	print(F)


from fractions import Fraction as F
mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
ret = 1
cnt = 0
for x in a:
	if x < 0:
		b.append((-x, 0))
	else:
		b.append((x, 1))
b.sort(reverse=True)
p = -1
m = -1
for i in range(k):
	ret *= b[i][0]
	ret %= mod
	if b[i][1] == 0:
		cnt += 1
		m = i
	else:
		p = i
if cnt % 2 == 0:
	print(ret)
	exit()
ret1 = -1
ret2 = -1
f1 = f2 = 0
if p != -1:
	ret1 = ret * pow(b[p][0], mod - 2, mod) % mod
	for i in range(k, n):
		if b[i][1] == 0:
			ret1 *= b[i][0]
			ret1 %= mod
			f1 = 1
			val1 = F(b[i][0], b[p][0])
			break
if m != -1:
	ret2 = ret * pow(b[m][0], mod - 2, mod) % mod
	for i in range(k, n):
		if b[i][1] == 1:
			ret2 *= b[i][0]
			ret2 %= mod
			f2 = 1
			val2 = F(b[i][0], b[m][0])
			break
if f1 == 0:
	ret1 = -1
if f2 == 0:
	ret2 = -1
if ret1 == ret2 == -1:
	ret = -1
	for i in range(k):
		ret *= b[-i - 1][0]
		ret %= mod
	print(ret % mod)
elif ret1 == -1:
	print(ret2)
elif ret2 == -1:
	print(ret1)
elif val1 > val2:
	print(ret1)
else:
	print(ret2)


from functools import reduce
from collections import deque

def prod(x, y):
	return x * y % MOD
(N, K) = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
MOD = 10 ** 9 + 7
if K % 2 == 1:
	flg = True
	for a in a_list:
		if a >= 0:
			flg = False
			break
	if flg:
		print(reduce(prod, a_list[:K]))
		exit()
S = []
a_list = deque(a_list)
i = 0
while i < K:
	if len(a_list) >= 2:
		if a_list[0] * a_list[1] >= a_list[-1] * a_list[-2]:
			S.append(a_list.popleft())
			i += 1
		elif a_list[0] * a_list[1] < a_list[-1] * a_list[-2] and i <= K - 2:
			S.append(a_list.pop())
			S.append(a_list.pop())
			i += 2
		else:
			S.append(a_list.popleft())
			i += 1
	else:
		S.append(a_list.popleft())
		i += 1
ans = reduce(prod, S)
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a_pos = sorted([i for i in a if i >= 0])
a_neg = sorted([i for i in a if i < 0], reverse=True)
mod = 10 ** 9 + 7
ans = 1
if len(a_pos) == 0 and k % 2:
	for i in a_neg[:k]:
		ans = ans * i % mod
	print(ans)
	exit()
while k > 0:
	if k == 1 or len(a_neg) <= 1:
		if len(a_pos) == 0:
			ans *= a_neg.pop()
		elif len(a_pos) > 0:
			ans *= a_pos.pop()
		k -= 1
	elif len(a_pos) <= 1:
		ans *= a_neg.pop() * a_neg.pop()
		k -= 2
	elif a_pos[-1] * a_pos[-2] > a_neg[-1] * a_neg[-2]:
		ans *= a_pos.pop()
		k -= 1
	elif a_pos[0] * a_pos[1] <= a_neg[-1] * a_neg[-2]:
		ans *= a_neg.pop() * a_neg.pop()
		k -= 2
	ans %= mod
else:
	print(ans)


mod = 1000000007

def sgn(v):
	return (v > 0) - (v < 0)

def solve():
	v.sort(key=abs, reverse=True)
	res = 1
	flag = 1
	for i in range(k):
		res *= v[i]
		res %= mod
		flag *= sgn(v[i])
	if flag >= 0:
		return res
	if max(v) <= 0:
		res = 1
		for i in range(-k, 0, 1):
			res *= v[i]
			res %= mod
		return res

	def get(comp):
		i = k - 1
		while i >= 0 and comp(v[i]):
			i -= 1
		j = k
		while j < n and (not comp(v[j])):
			j += 1
		if j == n:
			j = i
		return (i, j)
	(i, j) = get(lambda w: w >= 0)
	(i2, j2) = get(lambda w: w <= 0)
	if i2 >= 0 and v[j] * v[i2] < v[i] * v[j2]:
		i = i2
		j = j2
	res = v[j]
	for a in range(k):
		if a != i:
			res *= v[a]
			res %= mod
	return res
(n, k) = map(int, input().split(' '))
v = list(map(int, input().split(' ')))
print(solve())


from bisect import bisect_left
(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())))
pos = A[bisect_left(A, 0):]
pos.reverse()
neg = A[:bisect_left(A, 0)]
mod = 10 ** 9 + 7
ans = 1
if len(pos) == 0 and K % 2 == 1:
	for i in range(K):
		ans *= neg[-i - 1]
		ans %= mod
elif N == K:
	for i in range(K):
		ans *= A[i]
		ans %= mod
else:
	(p, n) = (0, 0)
	for i in range(0, K - 1, 2):
		v1 = 0
		v2 = 0
		if K % 2 == 0:
			if len(pos) >= p + 2:
				v1 = pos[p] * pos[p + 1]
		elif len(pos) >= p + 3:
			v1 = pos[p] * pos[p + 1]
		if len(neg) >= n + 2:
			v2 = neg[n] * neg[n + 1]
		if v2 > v1:
			ans *= v2
			ans %= mod
			n += 2
		else:
			ans *= v1
			ans %= mod
			p += 2
	if K % 2 == 1:
		ans *= pos[p]
		ans %= mod
print(ans)


(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
MOD = 10 ** 9 + 7
if N == K:
	ans = 1
	for i in A:
		ans = ans * i % MOD
	print(ans)
	exit()
if K == 1:
	print(A[0] % MOD)
	exit()
if K % 2 == 1 and A[0] == 0:
	print(0)
	exit()
if K % 2 == 1 and A[0] < 0:
	ans = 1
	for i in range(K):
		ans = ans * A[i] % MOD
	print(ans)
	exit()
if N - A.count(0) < K:
	print(0)
	exit()
if A[-1] >= 0:
	ans = 1
	for i in range(K):
		ans = ans * A[i] % MOD
	print(ans)
	exit()
l = 0
r = N - 1
t = []
c = 0
if K % 2 == 1:
	tk = K - 1
	flg = True
else:
	tk = K
	flg = False
while c < tk:
	if A[l] * A[l + 1] <= A[r] * A[r - 1]:
		t.append(A[r])
		t.append(A[r - 1])
		r -= 2
		c += 2
	else:
		t.append(A[l])
		t.append(A[l + 1])
		l += 2
		c += 2
if flg:
	t.append(A[l])
ans = 1
for i in t:
	ans = ans * i % MOD
print(ans)


(n, k) = map(int, input().split(' '))
l = map(int, input().split(' '))
s = 1
if n == k:
	for i in l:
		s *= i
		s %= 1000000007
	print(s)
else:
	pos = []
	neg = []
	for i in l:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)
	pos.sort()
	neg.sort(reverse=True)
	answer = []
	if k % 2 == 1 and (not pos):
		for i in range(k):
			s *= neg[i]
			s %= 1000000007
		print(s)
	else:
		if k % 2 == 1:
			s = pos.pop()
		for i in range(k // 2):
			if len(pos) >= 2:
				answer.append(pos.pop() * pos.pop())
			else:
				break
		for i in range(k // 2):
			if len(neg) >= 2:
				answer.append(neg.pop() * neg.pop())
			else:
				break
		answer.sort(reverse=True)
		for i in range(k // 2):
			s *= answer[i]
			s %= 1000000007
		print(s)


DE = 10 ** 9 + 7
(N, K) = list(map(lambda x: int(x), input().split(' ')))
A = list(map(lambda x: int(x), input().split(' ')))

def main():
	A_posi = []
	A_nega = []
	for a in A:
		if a > 0:
			A_posi.append(a)
		elif a < 0:
			A_nega.append(-a)
	len_posi = len(A_posi)
	len_nega = len(A_nega)
	if len_posi + len_nega < K:
		return 0
	if len_nega % 2 == 1 and K == len_posi + len_nega or (K % 2 == 1 and len_posi == 0):
		if len_posi + len_nega == N:
			A_posi.sort()
			A_nega.sort()
			answer = 1
			k = 0
			for a in A_nega:
				answer *= -a % DE
				answer %= DE
				k += 1
				if k >= K:
					break
			else:
				for a in A_posi:
					answer *= a % DE
					answer %= DE
					k += 1
					if k >= K:
						break
			return answer
		else:
			return 0
	A_posi.sort(reverse=True)
	A_nega.sort(reverse=True)
	posi = 0
	nega = 0
	answer = 1
	if K % 2 == 1:
		answer = A_posi[0] % DE
		posi = 1
	while posi + nega + 2 <= K:
		p = A_posi[posi] * A_posi[posi + 1] if posi + 1 < len_posi else 0
		n = A_nega[nega] * A_nega[nega + 1] if nega + 1 < len_nega else 0
		if p > n:
			answer *= p % DE
			answer %= DE
			posi += 2
		else:
			answer *= n % DE
			answer %= DE
			nega += 2
	return answer
print(main())


MOD = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
(aplus, aminus) = ([], [])
for i in range(n):
	if a[i] >= 0:
		aplus.append(a[i])
	else:
		aminus.append(a[i])
if len(aplus) == 0 and k % 2 == 1:
	asort = sorted(a, reverse=True)
	ans = 1
	for i in range(k):
		ans = ans * asort[i] % MOD
	print(ans)
	return
if n == k:
	ans = 1
	for i in range(k):
		ans = ans * a[i] % MOD
	print(ans)
	return
newa = sorted(a, reverse=True, key=abs)
newaplus = sorted(aplus, reverse=True)
newaminus = sorted(aminus)
(cntp, cntm, pp, mm) = (0, 0, 0, 0)
for i in range(k):
	if newa[i] >= 0:
		cntp += 1
		pp = i
	else:
		cntm += 1
		mm = i
if cntm % 2 == 1:
	if cntp == 0:
		newa[mm] = newaplus[cntp]
	elif len(newaplus) == cntp:
		newa[pp] = newaminus[cntm]
	elif len(newaminus) == cntm:
		newa[mm] = newaplus[cntp]
	elif newa[pp] * newaplus[cntp] >= newa[mm] * newaminus[cntm]:
		newa[mm] = newaplus[cntp]
	else:
		newa[pp] = newaminus[cntm]
ans = 1
for i in range(k):
	ans = ans * newa[i] % MOD
print(ans)


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr.sort(reverse=True)
absarr = [[abs(i), 1 if i > 0 else -1 if i < 0 else 0] for i in arr]
absarr.sort(reverse=True, key=lambda x: x[0])
mod = 10 ** 9 + 7
zeroflag = True if absarr[-1][0] == 0 else False
from collections import Counter
posnegarr = Counter([i[1] for i in absarr[:k]])
pos = posnegarr[1]
neg = posnegarr[-1]
if absarr[k - 1] == 0:
	ans = 0
elif neg % 2 == 0 or n == k:
	ans = 1
	for i in absarr[:k]:
		ans *= i[0]
		ans %= mod
	if n == k and neg % 2 == 1:
		ans = -ans % mod
else:
	ans = 1
	for i in absarr[:k]:
		ans *= i[0]
		ans %= mod
	if pos > 0:
		if absarr[k][0] == 0:
			ans = 0
		nextpos = nextneg = 0
		tmp = k
		while tmp < n and (nextpos == 0 or nextneg == 0):
			num = absarr[tmp]
			if num[0] == 0:
				break
			elif num[1] > 0 and nextpos == 0:
				nextpos = num[0]
			elif num[1] < 0 and nextneg == 0:
				nextneg = num[0]
			tmp += 1
		backpos = backneg = 0
		tmp = k - 1
		while backpos == 0 or backneg == 0:
			num = absarr[tmp]
			if num[1] > 0 and backpos == 0:
				backpos = num[0]
			elif num[1] < 0 and backneg == 0:
				backneg = num[0]
			tmp -= 1
		if ans == 0:
			pass
		elif nextpos * backpos > nextneg * backneg:
			ans *= nextpos * pow(backneg, -1, mod)
			ans %= mod
		else:
			ans *= nextneg * pow(backpos, -1, mod)
			ans %= mod
	else:
		nextpos = 0
		tmp = k
		while tmp < n and nextpos == 0:
			num = absarr[tmp]
			if num[1] > 0:
				nextpos = num[0]
			tmp += 1
		backneg = absarr[k - 1][0]
		if nextpos != 0:
			ans *= nextpos * pow(backneg, -1, mod)
			ans %= mod
		elif zeroflag:
			ans = 0
		else:
			ans = 1
			for i in arr[:k]:
				ans *= i
				ans %= mod
print(ans)


def prod(list):
	prod = 1
	for k in list:
		prod = prod * k % (10 ** 9 + 7)
	return prod
(n, kk) = map(int, input().split())
a = list(map(int, input().split()))
plus = []
minus = []
for k in a:
	if k >= 0:
		plus.append(k)
	if k <= 0:
		minus.append(k)
if len(plus) == 0:
	if kk % 2 == 0:
		mi = sorted(minus)
		ans = prod(mi[:kk])
	else:
		mi = sorted(minus, reverse=True)
		ans = prod(mi[:kk])
	print(int(ans) % (10 ** 9 + 7))
elif n == kk:
	ans = prod(a)
	print(int(ans) % (10 ** 9 + 7))
else:
	mi = sorted(minus)
	pl = sorted(plus, reverse=True)
	mi.append(0)
	mi.append(0)
	pl.append(0)
	pl.append(0)
	miind = 0
	plind = 0
	ans = 1
	while kk > miind + plind:
		if mi[miind] * mi[miind + 1] > pl[plind] * pl[plind + 1] and kk != miind + plind + 1:
			ans = ans * mi[miind] * mi[miind + 1] % (10 ** 9 + 7)
			miind += 2
		else:
			ans = ans * pl[plind] % (10 ** 9 + 7)
			plind += 1
	print(ans)


from heapq import heapify, heappush, heappop
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 1000000007
B = [a for a in A if a > 0]
C = [a for a in A if a <= 0]
B.sort()
C.sort(reverse=True)
ans = 1
if N == K:
	for a in A:
		ans *= a
		ans %= MOD
elif len(B) == 0 and K % 2 == 1:
	for i in range(K):
		ans *= C[i]
		ans %= MOD
else:
	if K % 2 == 1:
		ans *= B[-1]
		B.pop()
		K -= 1
	i = 0
	j = 0
	k = 0
	while k < K:
		flag = 0
		if len(B) >= 2 and len(C) >= 2 and (B[-1] * B[-2] < C[-1] * C[-2]):
			flag = 1
		elif len(B) <= 1 and len(C) >= 2:
			flag = 1
		elif len(B) == 1 and len(C) == 1:
			flag = 2
		if flag == 0:
			ans *= B[-1] * B[-2]
			ans %= MOD
			B.pop()
			B.pop()
		elif flag == 1:
			ans *= C[-1] * C[-2]
			ans %= MOD
			C.pop()
			C.pop()
		elif flag == 2:
			ans *= C[-1] * B[-1]
			ans %= MOD
			B.pop()
			C.pop()
		k += 2
print(ans)


(N, K) = map(int, input().split())
(*A,) = map(int, input().split())
B = [a for a in A if a >= 0]
B.sort()
C = [a for a in A if a < 0]
C.sort(reverse=True)
ans = 1
MOD = 10 ** 9 + 7
if len(B) == 0 and K % 2 == 1:
	C.sort()
	for _ in [0] * K:
		ans *= C.pop()
		ans %= MOD
	print(ans)
	exit()
if K == N:
	for a in A:
		ans = ans * a % MOD
	print(ans)
	exit()
while K >= 2:
	if len(B) >= 2 and len(C) >= 2:
		if B[-1] * B[-2] > C[-1] * C[-2]:
			ans *= B.pop() * B.pop() % MOD
			ans %= MOD
			K -= 2
		else:
			ans *= C.pop() * C.pop() % MOD
			ans %= MOD
			K -= 2
	elif len(C) >= 2:
		ans *= C.pop() * C.pop() % MOD
		ans %= MOD
		K -= 2
	else:
		ans *= B.pop()
		ans %= MOD
		K -= 1
if K == 1:
	ans *= B.pop()
	ans %= MOD
ans %= MOD
print(ans)


(N, K) = map(int, input().split())
A = sorted([int(a) for a in input().split()], key=lambda x: -abs(x))
P = 10 ** 9 + 7
m = 0
ans = 1
lp = 0
lm = 0
np = 0
nm = 0
for a in A[:K]:
	if a > 0:
		lp = a
		ans = ans * a % P
	elif a < 0:
		lm = a
		m ^= 1
		ans = ans * a % P
	else:
		print(0)
		exit()
if m == 0:
	print(ans)
	exit()
for a in A[K:]:
	if a > 0:
		np = a
		break
for a in A[K:]:
	if a < 0:
		nm = a
		break
if lp and nm and lm and np:
	if lp * np > lm * nm:
		print(ans * pow(lm, P - 2, P) * np % P)
	else:
		print(ans * pow(lp, P - 2, P) * nm % P)
elif lp and nm:
	print(ans * pow(lp, P - 2, P) * nm % P)
elif lm and np:
	print(ans * pow(lm, P - 2, P) * np % P)
else:
	A = A[::-1][:K]
	ans = 1
	for a in A:
		ans = ans * a % P
	print(ans)


3
import numpy
MAX = 10 ** 9 + 7

def prod_mod(la, mod):
	x = 1
	for a in la:
		x *= a
		x %= mod
	return x

def main():
	(n, k) = list(map(int, input().strip().split()))
	la = numpy.array(list(map(int, input().strip().split())))
	la.sort()
	if n == k:
		print(prod_mod(la, MAX))
	elif k % 2 == 1 and (la >= 0).sum() == 0:
		print(prod_mod(la[-k:], MAX))
	else:
		(il, ir) = (0, n - 1)
		cnt = 0
		l = []
		if k % 2 == 1:
			l.append(la[ir])
			ir -= 1
			cnt += 1
		while k - (cnt + 2) >= 0:
			if la[il] * la[il + 1] > la[ir - 1] * la[ir]:
				l.extend([la[il], la[il + 1]])
				il += 2
			else:
				l.extend([la[ir - 1], la[ir]])
				ir -= 2
			cnt += 2
		print(prod_mod(l, MAX))

def __starting_point():
	main()
__starting_point()


from collections import deque
(N, K) = map(int, input().split())
table = list(map(int, input().split()))
jnum = K - sum((1 for i in table if i >= 0))
num_mins = sum((1 for i in table if i < 0))
q_plus = deque(sorted([i for i in table if i >= 0], reverse=True))
q_mins = deque(sorted([-i for i in table if i < 0], reverse=True))
s_plus = []
s_mins = []
total = 1
if K % 2 == 1 and N == num_mins or (N == K and num_mins % 2 == 1):
	for i in range(K):
		if not q_plus:
			total = -total * q_mins.pop() % (10 ** 9 + 7)
		elif not q_mins:
			total = total * q_plus.pop() % (10 ** 9 + 7)
		elif q_plus[-1] > q_mins[-1]:
			total = -total * q_mins.pop() % (10 ** 9 + 7)
		else:
			total = total * q_plus.pop() % (10 ** 9 + 7)
	total = total % (10 ** 9 + 7)
else:
	for i in range(K):
		if not q_plus:
			s_mins.append(q_mins.popleft())
		elif not q_mins:
			s_plus.append(q_plus.popleft())
		elif q_plus[0] > q_mins[0]:
			s_plus.append(q_plus.popleft())
		else:
			s_mins.append(q_mins.popleft())
	if len(s_mins) % 2 == 1:
		if not q_plus:
			s_plus[-1] = q_mins[0]
		elif not q_mins or not s_plus:
			s_mins[-1] = q_plus[0]
		elif q_mins[0] * s_mins[-1] > q_plus[0] * s_plus[-1]:
			s_plus[-1] = q_mins[0]
		else:
			s_mins[-1] = q_plus[0]
	s_plus.extend(s_mins)
	for j in s_plus:
		total = total * j % (10 ** 9 + 7)
print(total)


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
(s, t) = ([], [])
for i in a:
	if i < 0:
		t.append(i)
	else:
		s.append(i)
(S, T) = (len(s), len(t))
is_positive = False
if S > 0:
	if n == k:
		is_positive = T % 2 == 0
	else:
		is_positive = True
else:
	is_positive = k % 2 == 0
ans = 1
if not is_positive:
	a.sort(key=abs)
	for i in range(k):
		ans = ans * a[i] % MOD
else:
	s.sort()
	t.sort(reverse=True)
	if k % 2 == 1:
		ans = ans * s.pop(-1) % MOD
	p = []
	while len(s) >= 2:
		x = s.pop(-1)
		x *= s.pop(-1)
		p.append(x)
	while len(t) >= 2:
		x = t.pop(-1)
		x *= t.pop(-1)
		p.append(x)
	p.sort(reverse=True)
	for i in range(k // 2):
		ans = ans * p[i] % MOD
print(ans)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	a.sort()
	ret = 1
	if k % 2 == 0 or a[-1] >= 0:
		l = 0
		r = -1
		mlt1 = a[0] * a[1]
		mlt2 = a[-2] * a[-1]
		for _ in range(k // 2):
			if mlt1 >= mlt2:
				ret *= mlt1 % mod
				l += 2
				if l <= n - 2:
					mlt1 = a[l + 1] * a[l]
			else:
				ret *= mlt2 % mod
				r -= 2
				if r >= -n + 1:
					mlt2 = a[r - 1] * a[r]
			ret %= mod
		if k % 2 == 1:
			ret *= a[r]
			ret %= mod
	else:
		for i in range(k):
			ret *= a[n - 1 - i]
			ret %= mod
	print(ret)
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
if max(a) < 0 and k % 2 or n == k:
	ans = 1
	for i in range(n - k, n):
		ans *= a[i]
		ans %= mod
	print(ans)
	exit()
cntn = 0
cntp = n - 1
if k % 2:
	ans = a[-1]
	cntp -= 1
	n -= 1
else:
	ans = 1
for i in range(k // 2):
	tmp = 0
	if (cntn < n - 1 and a[cntn + 1] < 0) and (cntp > 0 and a[cntp - 1] >= 0):
		if a[cntn] * a[cntn + 1] > a[cntp - 1] * a[cntp]:
			tmp = a[cntn] * a[cntn + 1]
			cntn += 2
		else:
			tmp = a[cntp - 1] * a[cntp]
			cntp -= 2
	elif cntn < n - 1 and a[cntn + 1] < 0:
		tmp = a[cntn] * a[cntn + 1]
		cntn += 2
	else:
		tmp = a[cntp - 1] * a[cntp]
		cntp -= 2
	ans *= tmp
	ans %= mod
print(ans)


(N, K) = map(int, input().split())
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
Ap = [a for a in A if a >= 0]
An = [-a for a in A if a < 0]
Ap.sort()
Ap.reverse()
An.sort()
An.reverse()
if len(Ap) == 0 and K % 2 == 1:
	ans = 1
	An.reverse()
	for i in range(K):
		ans = ans * -An[i] % MOD
	print(ans)
	exit()
B = [(a, 1) if a >= 0 else (-a, -1) for a in A]
B.sort()
B.reverse()
M = [0 if B[0][1] > 0 else 1]
for i in range(1, N):
	M.append(M[i - 1] + (0 if B[i][1] > 0 else 1))
i = K - 1
if M[i] % 2 == 0 or K == N:
	ans = 1
	v = 1 if M[i] % 2 == 0 else -1
	for j in range(K):
		ans = ans * B[j][0] % MOD
	print(ans * v % MOD)
else:
	n = M[i]
	p = K - n
	if len(An) == n or p == 0:
		n -= 1
		p += 1
	elif len(Ap) == p:
		n += 1
		p -= 1
	elif Ap[p - 1] * Ap[p] >= An[n - 1] * An[n]:
		n -= 1
		p += 1
	else:
		n += 1
		p -= 1
	ans = 1
	for i in range(p):
		ans = ans * Ap[i] % MOD
	for i in range(n):
		ans = ans * An[i] % MOD
	print(ans)


MOD = 10 ** 9 + 7
ans = 1
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if n == k:
	for x in a:
		ans *= x
		ans %= MOD
	print(ans % MOD)
	exit()
pos = []
neg = []
for x in a:
	if x >= 0:
		pos.append(x)
	else:
		neg.append(x)
pos.sort(reverse=True)
neg.sort()
if len(pos) == 0 and k % 2:
	for i in range(1, k + 1):
		ans *= neg[-i]
		ans %= MOD
	print(ans % MOD)
	exit()
pi = 0
ni = 0
if k % 2:
	ans *= pos[pi]
	pi += 1
	k -= 1
while k > 0:
	if pi < len(pos) - 1:
		sp = pos[pi] * pos[pi + 1]
	else:
		sp = 0
	if ni < len(neg) - 1:
		sn = neg[ni] * neg[ni + 1]
	else:
		sn = 0
	if sp > sn:
		ans *= sp
		pi += 2
	else:
		ans *= sn
		ni += 2
	ans %= MOD
	k -= 2
print(ans % MOD)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
plus = []
minus = []
for i in A:
	if i >= 0:
		plus.append(i)
	else:
		minus.append(i)
ok = False
if len(plus) > 0:
	if n == k:
		ok = len(minus) % 2 == 0
	else:
		ok = True
else:
	ok = k % 2 == 0
ans = 1
if not ok:
	A.sort(key=abs)
	for i in range(k):
		ans *= A[i]
		ans %= mod
else:
	plus.sort()
	minus.sort(reverse=True)
	if k % 2 == 1:
		ans *= plus.pop()
	P = []
	while len(plus) >= 2:
		P.append(plus.pop() * plus.pop())
	while len(minus) >= 2:
		P.append(minus.pop() * minus.pop())
	P.sort(reverse=True)
	for i in range(k // 2):
		ans *= P[i]
		ans %= mod
print(ans)


MOD = 1000000007

def maxProductSubarrayOfSizeK(A, n, k):
	A.sort()
	product = 1
	if A[n - 1] == 0 and k & 1:
		return 0
	if A[n - 1] < 0 and k & 1:
		A.reverse()
		for i in range(k):
			product *= A[i]
			if abs(product) >= MOD:
				product = product % MOD
		return product
	i = 0
	j = n - 1
	if k & 1:
		product *= A[j]
		product %= MOD
		j -= 1
		k -= 1
	k >>= 1
	for itr in range(k):
		left_product = A[i] * A[i + 1]
		right_product = A[j] * A[j - 1]
		if left_product > right_product:
			product *= left_product
			product %= MOD
			i += 2
		else:
			product *= right_product
			product %= MOD
			j -= 2
	return product
(n, k) = map(int, input().split(' '))
numbers = [int(x) for x in input().split(' ')]
ans = maxProductSubarrayOfSizeK(numbers, n, k)
print((ans + MOD) % MOD)


def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	MOD = 10 ** 9 + 7
	ans = 1
	if K % 2 == 1 and A[-1] < 0:
		for i in range(K):
			ans = ans * A[N - (i + 1)] % MOD
		print(ans)
		return
	l = 0
	r = N - 1
	if K % 2 == 1:
		ans = ans * A[r]
		r -= 1
	for _ in range(K // 2):
		ml = A[l] * A[l + 1]
		mr = A[r] * A[r - 1]
		if ml > mr:
			ans = ans * ml % MOD
			l += 2
		else:
			ans = ans * mr % MOD
			r -= 2
	print(ans)
	return
main()


def func(A, n, k):
	A.sort()
	product = 1
	if A[n - 1] == 0 and k & 1:
		return 0
	if A[n - 1] <= 0 and k & 1:
		for i in range(n - 1, n - k - 1, -1):
			product = product * A[i] % mod
		return product
	i = 0
	j = n - 1
	if k & 1:
		product = product * A[j] % mod
		j -= 1
		k -= 1
	k >>= 1
	for itr in range(k):
		left_product = A[i] * A[i + 1]
		right_product = A[j] * A[j - 1]
		if left_product > right_product:
			product = product * (left_product % mod) % mod
			i += 2
		else:
			product = product * (right_product % mod) % mod
			j -= 2
	return product
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
global mod
mod = 1000000007
ans = func(arr, n, k)
print(ans % mod)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ans = 1
if n == k:
	for x in a:
		ans *= x
		ans %= MOD
	print(ans % MOD)
elif max(a) < 0 and k % 2:
	a.sort()
	for i in range(1, k + 1):
		ans *= a[-i]
		ans %= MOD
	print(ans % MOD)
else:
	pos = []
	neg = []
	for x in a:
		if x >= 0:
			pos.append(x)
		else:
			neg.append(x)
	pos.sort(reverse=True)
	neg.sort()
	if k % 2:
		ans *= pos.pop(0)
		k -= 1
	num = []
	for (x, y) in zip(pos[::2], pos[1::2]):
		num.append(x * y)
	for (x, y) in zip(neg[::2], neg[1::2]):
		num.append(x * y)
	num.sort(reverse=True)
	for i in range(k // 2):
		ans *= num[i]
		ans %= MOD
	print(ans % MOD)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mod = 10 ** 9 + 7
ans = 1
if K % 2 == 1 and A[-1] < 0:
	for i in range(K):
		ans = ans * A[N - (i + 1)] % mod
	print(ans)
	exit()
l = 0
r = N - 1
if K % 2 == 1:
	ans = ans * A[r]
	r -= 1
for _ in range(K // 2):
	ml = A[l] * A[l + 1]
	mr = A[r] * A[r - 1]
	if ml > mr:
		ans = ans * ml % mod
		l += 2
	else:
		ans = ans * mr % mod
		r -= 2
print(ans)


def main():
	import sys

	def input():
		return sys.stdin.readline().rstrip()
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	ans = 1

	def answer(a):
		ans = 1
		for x in a:
			ans *= x
			ans %= mod
		return ans
	if n == k:
		print(answer(a))
		return
	a.sort(reverse=True, key=lambda x: abs(x))
	if sum((x < 0 for x in a[:k])) % 2 == 0:
		print(answer(a[:k]))
	elif all((x < 0 for x in a)):
		print(answer(a[-k:]))
	else:
		try:
			(x1, y1) = (min([x for x in a[:k] if x > 0]), min([x for x in a[k:] if x < 0]))
		except ValueError:
			(x1, y1) = (1, 0)
		try:
			(x2, y2) = (max([x for x in a[:k] if x < 0]), max([x for x in a[k:] if x >= 0]))
		except ValueError:
			(x2, y2) = (1, 0)
		if abs(x2 * y1) > abs(x1 * y2):
			a[a.index(x1)] = y1
		else:
			a[a.index(x2)] = y2
		print(answer(a[:k]))

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
(p, n) = ([], [])
for i in range(N):
	if A[i] >= 0:
		p.append(A[i])
	else:
		n.append(A[i])
ok = False
if len(p) > 0:
	if N == K:
		if len(n) % 2 == 0:
			ok = True
	else:
		ok = True
elif K % 2 == 0:
	ok = True
if not ok:
	A.sort(key=lambda x: abs(x))
	ans = 1
	for Ai in A[:K]:
		ans *= Ai
		ans %= MOD
	print(ans)
	exit()
p.sort(reverse=True)
n.sort()
if K % 2 == 1:
	ans = p[0]
	p = p[1:]
else:
	ans = 1
l = []
for i in range(len(p) // 2):
	l.append(p[2 * i] * p[2 * i + 1])
for i in range(len(n) // 2):
	l.append(n[2 * i] * n[2 * i + 1])
l.sort(key=lambda x: abs(x), reverse=True)
for li in l[:K // 2]:
	ans *= li
	ans %= MOD
print(ans)


mod = 1000000007
(n, k) = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst)
p = 1
if lst[-1] == 0 and k % 2 != 0:
	print(0)
elif lst[-1] < 0 and k % 2 != 0:
	for i in range(n - 1, n - k - 1, -1):
		p = p % mod * lst[i] % mod % mod
	print(p % mod)
else:
	j = n - 1
	if k % 2 != 0:
		p *= lst[j]
		k -= 1
		j -= 1
	k = k // 2
	i = 0
	for x in range(k):
		if lst[i] * lst[i + 1] > lst[j] * lst[j - 1]:
			p = p % mod * lst[i] % mod * lst[i + 1] % mod % mod
			i += 2
		else:
			p = p % mod * lst[j] % mod * lst[j - 1] % mod % mod
			j -= 2
	print(p % mod)


MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 1
if A[-1] >= 0:
	for i in range(K):
		ans *= A[i]
		ans %= MOD
elif A[0] < 0:
	if K % 2 == 0:
		for i in range(K):
			ans *= A[N - 1 - i]
			ans %= MOD
	else:
		for i in range(K):
			ans *= A[i]
			ans %= MOD
else:
	(r, l) = (N - 1, 0)
	n = 0
	while n < K:
		if K - n == 1:
			ans *= A[l]
			ans %= MOD
			n += 1
		elif A[r] * A[r - 1] > A[l] * A[l + 1]:
			ans *= A[r] * A[r - 1]
			ans %= MOD
			r -= 2
			n += 2
		else:
			ans *= A[l]
			ans %= MOD
			l += 1
			n += 1
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = []
f = []
z = 0
for ai in a:
	if ai > 0:
		s.append(ai)
	elif ai < 0:
		f.append(-ai)
	else:
		z += 1
p = len(s)
q = len(f)
l = max(0, k - p)
h = min(k, q)
mod = 10 ** 9 + 7
if l > h:
	print(0)
	exit()
if l % 2 == 0 or h - l >= 1:
	if l % 2 == 0:
		c = l
	else:
		c = l + 1
	s.sort(reverse=True)
	f.sort(reverse=True)
	while c + 2 <= h:
		if f[c] * f[c + 1] > s[k - c - 1] * s[k - c - 2]:
			c += 2
		else:
			break
	ans = 1
	for i in range(c):
		ans = ans * f[i] % mod
	for i in range(k - c):
		ans = ans * s[i] % mod
	print(ans)
	exit()
if z > 0:
	print(0)
	exit()
m = s + f
m.sort()
ans = 1
for i in range(k):
	ans = ans * m[i] % mod
ans = -ans % mod
print(ans)


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a_i = list(map(int, input().split()))
list.sort(a_i)
ans = 1
isminus = False
if k % 2 == 0:
	left = 0
	right = n - 1
else:
	left = 0
	right = n - 2
	ans *= a_i[n - 1]
if ans < 0:
	isminus = True
for x in range(k // 2):
	ans_L = a_i[left] * a_i[left + 1]
	ans_R = a_i[right] * a_i[right - 1]
	if isminus == False and ans_L < ans_R or (isminus == True and ans_L > ans_R):
		ans *= ans_R
		right -= 2
	else:
		ans *= ans_L
		left += 2
	if ans < 0 or ans >= mod:
		ans %= mod
print(ans)


from bisect import bisect_left, bisect_right
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
na = a[:bisect_left(a, 0)]
pa = a[bisect_right(a, 0):][::-1]
mod = 10 ** 9 + 7
if k == n:
	ans = 1
	for i in a:
		ans *= i
		ans %= mod
	print(ans)
	exit(0)
if k % 2 == 1 and len(pa) == 0:
	ans = 1
	for i in a[::-1][:k]:
		ans *= i
		ans %= mod
	print(ans)
	exit(0)
if k == 1:
	print(a[-1])
	exit(0)
if k % 2 == 1:
	rem = pa[-1]
	pa = pa[:-1]
na += [0] * n
pa += [0] * n
nn = 0
pn = 0
ans = 1
for i in range(k // 2):
	if i == k // 2 - 1 and k % 2 == 1:
		break
	if pa[pn] * pa[pn + 1] >= na[nn] * na[nn + 1]:
		ans *= pa[pn] * pa[pn + 1]
		pn += 2
	else:
		ans *= na[nn] * na[nn + 1]
		nn += 2
	ans %= mod
if k % 2 == 1:
	ans *= max(pa[pn] * pa[pn + 1] * max(pa[pn + 2], rem), na[nn] * na[nn + 1] * max(pa[pn], rem))
print(ans % mod)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, k) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	res = 1
	if n == k:
		for a in A:
			res = res * a % mod
		print(res)
		return
	(P, M) = ([], [])
	for a in A:
		P.append(a) if a >= 0 else M.append(a)
	if len(P) == n:
		A.sort(reverse=True)
		for i in range(k):
			res = res * A[i] % mod
	elif len(M) == n:
		A.sort(reverse=True) if k % 2 else A.sort()
		for i in range(k):
			res = res * A[i] % mod
	else:
		P.sort(reverse=True)
		M.sort()
		B = []
		if k % 2:
			k -= 1
			b = P.pop(0)
			B.append(b)
			res = res * b % mod
		for i in range(0, len(P), 2):
			if i + 1 < len(P):
				B.append(P[i] * P[i + 1])
		for j in range(0, len(M), 2):
			if j + 1 < len(M):
				B.append(M[j] * M[j + 1])
		B.sort(reverse=True)
		for i in range(k // 2):
			res = res * B[i] % mod
	print(res)

def __starting_point():
	resolve()
__starting_point()


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 6)
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
mod = 10 ** 9 + 7
(n, k) = na()
a = na()
a.sort()
ans = 1
if k == 1:
	print(a[-1])
	exit()
if a[-1] <= 0 and k % 2 == 1:
	for i in range(n - k, n):
		ans = ans * a[i] % mod
	print(ans % mod)
	exit()
s = 0
e = -1
while k > 0:
	if k == 1:
		if a[s] >= a[e]:
			ans = ans * a[s] % mod
		else:
			ans = ans * a[e] % mod
		break
	p = a[s] * a[s + 1]
	q = a[e] * a[e - 1]
	if p >= q:
		ans = p % mod * ans % mod
		s += 2
	else:
		ans = q % mod * ans % mod
		e -= 2
	k -= 2
print(ans % mod)


def main():
	M = 10 ** 9 + 7
	(n, k, *a) = map(int, open(0).read().split())
	(x, y) = ([], [])
	for i in a:
		if i > 0:
			x += (i,)
		if i < 0:
			y += (i,)
	if len(x) + len(y) < k or (k % 2 and (not x) and (len(y) < n)):
		print(0)
		return
	if n == k or (k % 2 and (not x)):
		c = 1
		for i in sorted(x + y)[-k:]:
			c = c * i % M
		print(c)
		return
	x = sorted(x)[::-1][:k]
	i = len(x)
	y.sort()
	m = len(y)
	j = k - i
	if j % 2:
		x = x[:-1]
		i -= 1
		j += 1
	x += y[:j]
	while i > 1 and j + 1 < m and (x[i - 1] * x[i - 2] < y[j] * y[j + 1]):
		(x[i - 1], x[i - 2]) = (y[j], y[j + 1])
		i -= 2
		j += 2
	c = 1
	for i in x:
		c = c * i % M
	print(c)
main()


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
m = 10 ** 9 + 7
pos = [*filter(lambda x: x >= 0, A)]
neg = [*filter(lambda x: x < 0, A)]
pos.sort(reverse=True)
neg.sort()
ans = 1
(i, j) = (0, 0)
while i + j < K:
	flag = True
	if i == len(pos):
		flag = False
	elif j == len(neg):
		flag = True
	elif pos[i] < -neg[j]:
		flag = False
	if flag:
		ans = ans * pos[i] % m
		i += 1
	else:
		ans = ans * neg[j] % m
		j += 1
if j % 2 == 0 or N == K:
	print(ans)
elif len(pos) == 0:
	ans = 1
	for i in range(K):
		ans = ans * neg[len(neg) - 1 - i] % m
	print(ans)
else:
	flag2 = True
	if i == 0:
		flag2 = True
	elif j == 0:
		flag2 = False
	elif i == len(pos):
		flag2 = False
	elif j == len(neg):
		flag2 = True
	elif pos[i - 1] * pos[i] < neg[j - 1] * neg[j]:
		flag2 = False
	if flag2:
		ans = ans * pow(neg[j - 1], m - 2, m) % m * pos[i] % m
	else:
		ans = ans * pow(pos[i - 1], m - 2, m) % m * neg[j] % m
	print(ans)


(n, k) = (int(x) for x in input().split())
A = list((int(x) for x in input().split()))
MOD = 10 ** 9 + 7
A.sort()
l = 0
r = n - 1
flag = False
ans = 1
if k % 2 == 1:
	ans = A[r]
	r -= 1
	k -= 1
	if ans < 0:
		flag = True
if flag:
	while k:
		ans *= A[r] * A[r - 1] % MOD
		ans %= MOD
		r -= 2
		k -= 2
else:
	while k:
		x = A[l] * A[l + 1]
		y = A[r] * A[r - 1]
		if x > y:
			ans *= x % MOD
			ans %= MOD
			l += 2
		else:
			ans *= y % MOD
			ans %= MOD
			r -= 2
		k -= 2
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ans = 1
if K == N:
	for i in range(N):
		ans *= A[i]
		if ans > 0:
			ans = ans % MOD
elif max(A) <= 0 and K % 2 == 1:
	A.sort(reverse=True)
	for i in range(K):
		ans *= A[i]
		if ans > 0:
			ans = ans % MOD
else:
	Ap = []
	Am = []
	for i in range(N):
		if A[i] > 0:
			Ap.append(A[i])
		else:
			Am.append(A[i])
	Ap.sort(reverse=True)
	Am.sort()
	if K % 2 == 1 and Ap:
		ans *= Ap.pop(0)
	P = []
	for i in range(len(Ap) // 2):
		P.append(Ap[i * 2] * Ap[i * 2 + 1])
	for i in range(len(Am) // 2):
		P.append(Am[i * 2] * Am[i * 2 + 1])
	P.sort(reverse=True)
	for i in range(K // 2):
		ans *= P[i]
		ans = ans % MOD
print(ans % MOD)


mod = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())))
p = 1
n = 0
ans = 1
cnt = 0
while cnt < K - 1:
	if A[n] * A[n + 1] > A[-p] * A[-p - 1]:
		ans = ans * A[n] * A[n + 1] % mod
		n += 2
		cnt += 2
	else:
		ans = ans * A[-p] % mod
		p += 1
		cnt += 1
if cnt == K - 1:
	ans = ans * A[-p] % mod
if A[-1] < 0 and K % 2 == 1:
	ans = 1
	for i in A[N - K:]:
		ans = ans * i % mod
print(ans)


import sys
input = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
(pos, neg) = ([], [])
for a in A:
	if a < 0:
		neg.append(a)
	else:
		pos.append(a)
if pos:
	if N == K:
		ok = len(neg) % 2 == 0
	else:
		ok = True
else:
	ok = K % 2 == 0
ans = 1
if ok == False:
	A.sort(key=abs)
	for i in range(K):
		ans *= A[i]
		ans %= MOD
else:
	pos.sort()
	neg.sort(reverse=True)
	if K % 2:
		ans *= pos.pop()
	p = []
	while len(pos) >= 2:
		p.append(pos.pop() * pos.pop())
	while len(neg) >= 2:
		p.append(neg.pop() * neg.pop())
	p.sort(reverse=True)
	for i in range(K // 2):
		ans *= p[i]
		ans %= MOD
print(ans)


mod = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
neg = []
zero = 0
pos = []
for a in A:
	if a < 0:
		neg.append(a)
	else:
		pos.append(a)
pos.sort()
neg.sort(reverse=True)
if len(pos) == 0:
	res = 1
	if K % 2 == 0:
		neg.reverse()
	for a in neg[:K]:
		res *= a
		res %= mod
else:
	res = 1
	if K % 2 == 1:
		res = pos.pop()
		K -= 1
	while K > 1 and len(pos) > 1 and (len(neg) > 1):
		if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
			res *= pos.pop()
			res %= mod
			res *= pos.pop()
			res %= mod
		else:
			res *= neg.pop()
			res %= mod
			res *= neg.pop()
			res %= mod
		K -= 2
	while K > 1 and len(pos) > 1:
		res *= pos.pop()
		res %= mod
		res *= pos.pop()
		res %= mod
		K -= 2
	while K > 1 and len(neg) > 1:
		res *= neg.pop()
		res %= mod
		res *= neg.pop()
		res %= mod
		K -= 2
	while K and pos:
		res *= pos.pop()
		res %= mod
		K -= 1
	while K and neg:
		res *= neg.pop()
		res %= mod
		K -= 1
print(res)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
neg = 0
zero = 0
for i in range(n):
	if a[i] >= 0:
		if a[i] == 0:
			zero += 1
		a[i] = [a[i], 1]
	else:
		a[i] = [-a[i], 0]
		neg += 1
a.sort(reverse=True)
ans = 1
if n == k:
	for i in range(n):
		ans *= a[i][0]
		ans %= mod
		if not a[i][1]:
			ans *= -1
			ans %= mod
elif k % 2 == 1 and (neg == n or neg + zero == n):
	for i in range(1, k + 1):
		ans *= -a[-i][0]
		ans %= mod
else:
	(pos, neg) = (0, 0)
	(lastpos, lastneg) = (mod, mod)
	for i in range(k):
		ans *= a[i][0]
		ans %= mod
		if a[i][1]:
			pos += 1
			lastpos = a[i][0]
		else:
			neg += 1
			lastneg = a[i][0]
	if neg % 2 == 1:
		(firstpos, firstneg) = (mod, mod)
		for i in range(k, n):
			if not firstpos == mod and (not firstneg == mod):
				break
			if firstpos == mod and a[i][1]:
				firstpos = a[i][0]
			elif firstneg == mod and (not a[i][1]):
				firstneg = a[i][0]
		if not mod in [lastpos, lastneg, firstpos, firstneg]:
			if firstpos * lastpos >= firstneg * lastneg:
				ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
			else:
				ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
		elif not mod in [lastpos, firstneg]:
			ans = ans * pow(lastpos, mod - 2, mod) * firstneg % mod
		elif not mod in [lastneg, firstpos]:
			ans = ans * pow(lastneg, mod - 2, mod) * firstpos % mod
print(ans)


(N, K) = map(int, input().split())
X = list(map(int, input().split()))
MOD = 10 ** 9 + 7
pos = sorted((v for v in X if v >= 0))
neg = sorted((-v for v in X if v < 0))
ok = False
if pos:
	if N == K:
		ok = len(neg) % 2 == 0
	else:
		ok = True
else:
	ok = K % 2 == 0
ans = 1
if ok:
	if K % 2 == 1:
		ans = ans * pos.pop() % MOD
	cand = []
	while len(pos) >= 2:
		x = pos.pop() * pos.pop()
		cand.append(x)
	while len(neg) >= 2:
		x = neg.pop() * neg.pop()
		cand.append(x)
	cand.sort(reverse=True)
	for i in range(K // 2):
		ans = ans * cand[i] % MOD
else:
	cand = sorted(X, key=lambda x: abs(x))
	for i in range(K):
		ans = ans * cand[i] % MOD
print(ans)


(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
(D, E) = ([], [])
(zcnt, scnt, fcnt) = (0, 0, 0)
for i in A:
	if i == 0:
		zcnt += 1
		D.append(0)
	elif i > 0:
		D.append(i)
		scnt += 1
	else:
		E.append(i)
		fcnt += 1
mod = 10 ** 9 + 7
ans = 1
if K == N:
	for i in A:
		ans *= i
		ans %= mod
	print(ans)
	return
if K % 2 == 1 and max(A) < 0:
	A = sorted(A)[::-1]
	for i in range(K):
		ans *= A[i]
		ans %= mod
	print(ans)
	return
if K > scnt + fcnt:
	print(0)
	return
(D, E) = (sorted(D)[::-1], sorted(E))
ans = 1
cnt = 0
(a, b) = (0, 0)
while K - cnt > 1:
	if a + 1 <= len(D) - 1 and b + 1 <= len(E) - 1:
		(d, e) = (D[a] * D[a + 1], E[b] * E[b + 1])
		if d > e:
			ans *= D[a]
			a += 1
			cnt += 1
			ans %= mod
		else:
			ans *= e
			b += 2
			ans %= mod
			cnt += 2
	elif a + 1 <= len(D) - 1:
		d = D[a] * D[a + 1]
		ans *= D[a]
		a += 1
		cnt += 1
		ans %= mod
	elif b + 1 <= len(E) - 1:
		e = E[b] * E[b + 1]
		ans *= e
		b += 2
		cnt += 2
		ans %= mod
if K - cnt == 1:
	Z = []
	if a != scnt:
		Z.append(D[a])
	if b != fcnt:
		Z.append(E[-1])
	if 0 in A:
		Z.append(0)
	ans *= max(Z)
	ans %= mod
print(ans)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	ans = 1
	(s, t) = ([], [])
	for i in range(n):
		if a[i] < 0:
			t.append(a[i])
		else:
			s.append(a[i])
	(S, T) = (len(s), len(t))
	ok = False
	if S > 0:
		if n == k:
			ok = T % 2 == 0
		else:
			ok = True
	else:
		ok = k % 2 == 0
	if not ok:
		a.sort(key=abs)
		for i in range(k):
			ans *= a[i]
			ans %= mod
	else:
		s.sort()
		t.sort(reverse=True)
		if k % 2 == 1:
			ans *= s.pop()
			ans %= mod
		p = []
		while len(s) >= 2:
			x = s.pop()
			x *= s.pop()
			p.append(x)
		while len(t) >= 2:
			x = t.pop()
			x *= t.pop()
			p.append(x)
		p.sort(reverse=True)
		for i in range(k // 2):
			ans *= p[i]
			ans %= mod
	print(ans)
main()


def prod(li, MOD):
	ret = 1
	for a in li:
		ret *= a
		ret %= MOD
	return ret
(N, K) = map(int, input().split())
MOD = 1000000007
aaa = list(map(int, input().split()))
if N == K:
	print(prod(aaa, MOD))
	exit()
aaa.sort(key=lambda x: abs(x))
if sum((a < 0 for a in aaa[-K:])) % 2 == 0:
	print(prod(aaa[-K:], MOD))
else:
	if all((a <= 0 for a in aaa)):
		bbb = aaa[:K]
	else:
		try:
			(x1, y1) = (min([a for a in aaa[-K:] if a > 0]), min([a for a in aaa[:-K] if a < 0]))
		except:
			(x1, y1) = (1, 0)
		try:
			(x2, y2) = (max([a for a in aaa[-K:] if a < 0]), max([a for a in aaa[:-K] if a >= 0]))
		except:
			(x2, y2) = (1, 0)
		bbb = aaa[-K:]
		if abs(x2 * y1) > abs(x1 * y2):
			bbb.remove(x1)
			bbb.append(y1)
		else:
			bbb.remove(x2)
			bbb.append(y2)
	print(prod(bbb, MOD))


MOD = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
(p, q) = ([], [])
for x in a:
	if x >= 0:
		p.append(x)
	else:
		q.append(x)
(lp, lq) = (len(p), len(q))

def sp():
	p.sort(reverse=True)
	q.sort()
	ans = p[0] if k % 2 else 1
	s = []
	for i in range(0, lq - 1, 2):
		s.append(q[i] * q[i + 1])
	for i in range(k % 2, lp - 1, 2):
		s.append(p[i] * p[i + 1])
	s.sort(reverse=True)
	for i in range(k // 2):
		ans *= s[i]
		ans %= MOD
	print(ans)

def sq():
	a.sort(key=lambda x: abs(x))
	ans = 1
	for i in range(k):
		ans *= a[i]
		ans %= MOD
	print(ans)
if k % 2 and (not p):
	sq()
elif n == k and lq % 2:
	sq()
else:
	sp()


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
div = 7 + 10 ** 9
ans = 1
t = 0
(i, j) = (0, N - 1)
if A[-1] < 0 and K % 2 == 1:
	for i1 in range(N - K, N):
		ans *= A[i1]
		ans %= div
else:
	while t < K - 1:
		if A[i] * A[i + 1] > A[j] * A[j - 1]:
			ans *= A[i] * A[i + 1]
			ans %= div
			i += 2
			t += 2
		else:
			ans *= A[j]
			ans %= div
			j += -1
			t += 1
	if t == K - 1:
		ans *= A[j]
		ans %= div
print(ans)


(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
M = []
m = []
for a in A:
	if a < 0:
		m.append(abs(a))
	else:
		M.append(a)
i = 0
j = 0
tmp = 1
P = 10 ** 9 + 7
if K % 2 == 0 and len(m) // 2 * 2 + len(M) // 2 * 2 >= K or (K % 2 == 1 and len(M) + len(m) // 2 * 2 >= K and (len(M) > 0)):
	m.sort(reverse=True)
	M.sort(reverse=True)
	while K > 0:
		if K >= 2:
			if j + 2 <= len(M) and i + 2 <= len(m):
				if m[i] * m[i + 1] < M[j] * M[j + 1]:
					tmp *= M[j]
					j += 1
					K -= 1
				else:
					tmp *= m[i] * m[i + 1]
					i += 2
					K -= 2
			elif j + 2 <= len(M):
				tmp *= M[j]
				j += 1
				K -= 1
			elif i + 2 <= len(m):
				tmp *= m[i] * m[i + 1]
				i += 2
				K -= 2
			else:
				tmp *= m[i] * M[j]
		else:
			tmp *= M[j]
			K -= 1
		tmp %= P
else:
	m.sort()
	M.sort()
	for _ in range(K):
		if j + 1 <= len(M) and i + 1 <= len(m):
			if M[j] < m[i]:
				tmp *= M[j]
				j += 1
			else:
				tmp *= m[i]
				i += 1
		elif j + 1 <= len(M):
			tmp *= M[j]
			j += 1
		else:
			tmp *= m[i]
			i += 1
		tmp %= P
	tmp *= -1
	tmp %= P
print(tmp)


mod = 10 ** 9 + 7
(n, k, *A) = map(int, open(0).read().split())
if k == n:
	s = 1
	for a in A[:k]:
		s *= a
		s %= mod
	print(s)
elif k % 2 == 1 and all((a <= 0 for a in A)):
	A.sort(key=abs, reverse=1)
	s = A.pop() % mod
	c = 1
	while c < k:
		t = A.pop() * A.pop() % mod
		s *= t
		s %= mod
		c += 2
	print(s)
else:
	A.sort(key=abs)
	pos_A = [a for a in A if a >= 0]
	neg_A = [a for a in A if a <= 0]
	if k % 2 == 1:
		s = pos_A.pop()
		c = 1
	else:
		s = 1
		c = 0
	while c < k:
		if len(pos_A) >= 2 and len(neg_A) >= 2:
			if pos_A[-1] * pos_A[-2] > neg_A[-1] * neg_A[-2]:
				t = pos_A.pop() * pos_A.pop() % mod
			else:
				t = neg_A.pop() * neg_A.pop() % mod
		elif len(pos_A) < 2:
			t = neg_A.pop() * neg_A.pop() % mod
		else:
			t = pos_A.pop() * pos_A.pop() % mod
		s *= t
		s %= mod
		c += 2
	print(s)


import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda : sys.stdin.readline().rstrip()
i2n = lambda : int(i2s())
i2nn = lambda : s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
from collections import deque
from collections import defaultdict
from heapq import heapify, heappush, heappop, heappushpop
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(int(1000000.0))
MOD = int(1000000000.0) + 7

def main():
	(N, K) = i2nn()
	A = i2nn()
	if N == K:
		n = 1
		for a in A:
			n = n * a % MOD
		print(n)
		return
	Ap = [n for n in A if n >= 0]
	An = [-n for n in A if n < 0]
	Ap.sort()
	Ap.reverse()
	An.sort()
	An.reverse()
	Np = len(Ap)
	Nn = len(An)
	if N == Nn and K % 2 == 1:
		n = 1
		A.sort()
		A.reverse()
		for i in range(K):
			n = n * A[i] % MOD
		print(n)
		return
	n = 1
	k = K
	i = 0
	j = 0
	if k % 2 == 1:
		n = n * Ap[i] % MOD
		i += 1
		k -= 1
	while k > 0:
		if Np - i < 2:
			n = n * An[j] % MOD
			j += 1
			n = n * An[j] % MOD
			j += 1
		elif Nn - j < 2:
			n = n * Ap[i] % MOD
			i += 1
			n = n * Ap[i] % MOD
			i += 1
		else:
			np = Ap[i] * Ap[i + 1]
			nn = An[j] * An[j + 1]
			if np >= nn:
				n = n * np % MOD
				i += 2
			else:
				n = n * nn % MOD
				j += 2
		k -= 2
	print(n)
main()


(N, K) = map(int, input().split())
A = tuple(map(int, input().split()))
MOD = 10 ** 9 + 7
if K == N:
	ans = 1
	for x in A:
		ans = ans * x % MOD
	print(ans)
	exit()
(plus, minus) = ([], [])
for a in A:
	if a >= 0:
		plus.append(a)
	else:
		minus.append(a)
plus.sort(reverse=True)
minus.sort()
if not plus:
	ans = 1
	if K % 2:
		for x in minus[-K:]:
			ans = ans * x % MOD
	else:
		for x in minus[:K]:
			ans = ans * x % MOD
	print(ans)
	exit()
idx = 0
for i in range(2, N, 2):
	if K - i < 0:
		break
	if not len(plus) >= K - i + 2:
		idx += 2
		continue
	if len(minus) >= i:
		if minus[i - 2] * minus[i - 1] < plus[K - i + 1] * plus[K - i]:
			break
		else:
			idx += 2
ans = 1
for x in minus[:idx] + plus[:K - idx]:
	ans = ans * x % MOD
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(key=lambda x: -abs(x))
mod = 10 ** 9 + 7
p = 1
mm = 0
for i in range(k):
	if a[i] < 0:
		mm += 1
	p *= a[i]
	p %= mod
if n == k or mm % 2 == 0:
	print(p)
	exit()
m = 0
for i in a:
	if i <= 0:
		m += 1
if m == n:
	p = 1
	for i in range(k):
		p *= a[n - i - 1]
		p %= mod
	print(p)
	exit()
b1 = []
b2 = []
for i in range(k):
	if len(b1) == 0 and a[k - 1 - i] >= 0:
		b1.append(a[k - 1 - i])
	if len(b2) == 0 and a[k - 1 - i] < 0:
		b2.append(a[k - 1 - i])
for i in range(n - k):
	if len(b1) == 1 and a[k + i] < 0:
		b1.append(a[k + i])
	if len(b2) == 1 and a[k + i] >= 0:
		b2.append(a[k + i])
f = 0
if len(b1) == len(b2) == 2:
	if b1[1] * b2[0] >= b1[0] * b2[1]:
		f = 1
	else:
		f = 2
elif len(b2) < 2:
	f = 1
else:
	f = 2
if f == 1:
	p *= b1[1] * pow(b1[0], mod - 2, mod)
	print(p % mod)
	exit()
else:
	p *= b2[1] * pow(b2[0], mod - 2, mod)
	print(p % mod)
	exit()


from collections import deque
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
p = []
m = []
for i in a:
	if i >= 0:
		p.append(i)
	elif i < 0:
		m.append(i)
p.sort(reverse=True)
m.sort()
res = 1
if n == k:
	for i in a:
		res = res * i % mod
	print(res)
	exit()
if len(p) == 0 and k % 2 == 1:
	for i in range(k):
		res = res * m[-(i + 1)] % mod
	print(res)
else:
	p_ind = 0
	m_ind = 0
	while k:
		if k == 1:
			res = res * p[p_ind] % mod
			break
		temp = p[p_ind] * p[p_ind + 1] if p_ind + 1 < len(p) else 0
		temp1 = m[m_ind] * m[m_ind + 1] if m_ind + 1 < len(m) else 0
		if temp > temp1:
			res = res * p[p_ind] % mod
			p_ind += 1
			k -= 1
		else:
			res = res * temp1 % mod
			m_ind += 2
			k -= 2
	print(res)


import sys
input = sys.stdin.buffer.readline

def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	(l, r) = (0, N - 1)
	MOD = 10 ** 9 + 7
	if K == N:
		ans = 1
		for num in A:
			ans *= num
			ans %= MOD
		print(ans)
		exit()
	elif A[-1] < 0 and K % 2 == 1:
		ans = 1
		for i in range(K):
			ans *= A[-i - 1]
			ans %= MOD
		print(ans)
		exit()
	ans = 1
	if K % 2 == 1:
		ans *= A[-1]
		r -= 1
	for _ in range(K // 2):
		nl = A[l] * A[l + 1]
		nr = A[r] * A[r - 1]
		if nl > nr:
			ans *= nl
			l += 2
		else:
			ans *= nr
			r -= 2
		ans %= MOD
	print(ans)
main()


from collections import deque
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
A.sort(reverse=True)
ans = 1
B = deque(A)
if K % 2 == 1:
	ans *= B.popleft()
for _ in range(K // 2):
	l = B[0] * B[1]
	r = B[-1] * B[-2]
	if l >= r:
		ans *= B.popleft() * B.popleft()
	else:
		ans *= B.pop() * B.pop()
	if ans > 0:
		ans %= MOD
	else:
		ans = ans % MOD - MOD
if ans < 0:
	ans = 1
	for a in A[:K]:
		ans *= a
		ans %= MOD
print(ans % MOD)


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)
resolve()


MOD = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(key=abs, reverse=True)
s = 0
ps = 0
for i in range(k):
	if a[i] < 0:
		s ^= 1
	else:
		ps = 1
b = a[:k]
b.sort(key=abs)
if s:
	p = -MOD
	for i in range(k, n):
		if a[i] >= 0:
			p = a[i]
			break
	q = MOD
	if ps:
		for i in range(k, n):
			if a[i] <= 0:
				q = a[i]
				break
	x = 0
	for j in range(k):
		if b[j] < 0:
			x = b[j]
			xi = j
			break
	y = 0
	for j in range(k):
		if b[j] > 0:
			y = b[j]
			yi = j
			break
	flg = 1
	if y == 0:
		if p >= 0:
			b[xi] = p
			flg = 0
	else:
		if p * y > q * x and p > 0:
			b[xi] = p
		elif q < 0:
			b[yi] = q
		flg = 0
	if flg:
		b = a[-k:]
res = 1
for i in range(k):
	res = res * b[i] % MOD
print(res)


from math import log10
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
a.sort()
cnt_neg = 0
cnt_pos = 0
for i in a:
	if i <= 0:
		cnt_neg += 1
	else:
		cnt_pos += 1
is_minus = False
k_tmp = k
while k_tmp > 0:
	if k_tmp >= 2:
		if cnt_neg >= 2:
			cnt_neg -= 2
		elif cnt_pos >= 2:
			cnt_pos -= 2
		else:
			is_minus = True
			break
		k_tmp -= 2
	elif cnt_pos > 0:
		cnt_pos -= 1
		k_tmp -= 1
	else:
		is_minus = True
		break
k_1 = k
ans1 = 1
l = 0
r = n - 1
if k_1 % 2:
	ans1 *= a[-1]
	r -= 1
	k_1 -= 1
while k_1 >= 2:
	if a[l] * a[l + 1] > a[r - 1] * a[r]:
		ans1 *= a[l] * a[l + 1]
		l += 2
	else:
		ans1 *= a[r - 1] * a[r]
		r -= 2
	k_1 -= 2
	ans1 %= MOD
a.sort(key=abs)
ans2 = 1
for i in a[:k]:
	ans2 *= i
	ans2 %= MOD
if is_minus:
	print(ans2)
else:
	print(ans1)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = 1
mod = 10 ** 9 + 7
if 0 <= A[0]:
	for i in range(N - 1, N - K - 1, -1):
		ans = ans * A[i] % mod
elif A[-1] <= 0:
	if K % 2:
		for i in range(N - 1, N - K - 1, -1):
			ans = ans * A[i] % mod
	else:
		for i in range(K):
			ans = ans * A[i] % mod
else:
	l = 0
	r = N - 1
	if K % 2:
		ans = A[-1]
		r -= 1
		K -= 1
	while K:
		if A[l] * A[l + 1] < A[r] * A[r - 1]:
			ans = ans * A[r] * A[r - 1] % mod
			r -= 2
		else:
			ans = ans * A[l] * A[l + 1] % mod
			l += 2
		K -= 2
print(ans)


import sys
input = sys.stdin.readline
mod = int(1000000000.0 + 7)
(n, k) = map(int, input().split())
L = list(map(int, input().split()))
ans = 1
if k == n:
	for i in L:
		ans *= i
		ans %= mod
	print(ans % mod)
	sys.exit()
pos = []
neg = []
for i in L:
	if i >= 0:
		pos.append(i)
	else:
		neg.append(i)
pos.sort(reverse=True)
neg.sort()
if len(pos) == 0 and k % 2 != 0:
	for i in range(1, k + 1):
		ans *= neg[-i]
		ans %= mod
	print(ans % mod)
	sys.exit()
if k % 2 != 0:
	ans *= pos.pop(0)
	k -= 1
l = []
for i in range(1, len(pos), 2):
	l.append(pos[i] * pos[i - 1])
for i in range(1, len(neg), 2):
	l.append(neg[i] * neg[i - 1])
l.sort(reverse=True)
for i in range(k // 2):
	ans *= l[i]
	ans %= mod
print(ans % mod)


def main():
	mod = 10 ** 9 + 7
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort(key=lambda x: -abs(x))
	kouho = []
	minus = 0
	last_plus = None
	last_minus = None
	if k == 1:
		print(max(a))
		return
	for i in range(k):
		kouho.append(a[i])
		if a[i] >= 0:
			last_plus = a[i]
		if a[i] < 0:
			minus += 1
			last_minus = a[i]
	if minus % 2 == 0:
		ans = 1
		for i in kouho:
			ans = ans * i % mod
		print(ans)
		return
	change_plus = None
	change_minus = None
	if last_plus != None:
		for i in range(k, n):
			if a[i] <= 0:
				change_plus = a[i]
				break
	if last_minus != None:
		for i in range(k, n):
			if a[i] >= 0:
				change_minus = a[i]
				break
	if change_plus == None and change_minus == None:
		ans = 1
		for i in range(k):
			ans = ans * a[-i - 1] % mod
	elif change_plus == None:
		ans = change_minus
		for i in kouho:
			ans = ans * i % mod
		ans = ans * pow(last_minus, mod - 2, mod) % mod
	elif change_minus == None:
		ans = change_plus
		for i in kouho:
			ans = ans * i % mod
		ans = ans * pow(last_plus, mod - 2, mod) % mod
	elif abs(change_plus * last_minus) < abs(change_minus * last_plus):
		ans = change_minus
		for i in kouho:
			ans = ans * i % mod
		ans = ans * pow(last_minus, mod - 2, mod) % mod
	else:
		ans = change_plus
		for i in kouho:
			ans = ans * i % mod
		ans = ans * pow(last_plus, mod - 2, mod) % mod
	print(ans)
main()


(n, k) = map(int, input().split())
a = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
ans = 1
if n == k:
	for x in a:
		ans *= x
		ans %= mod
	print(ans)
	exit()
b = []
c = []
for x in a:
	if 0 <= x:
		b += [x]
	else:
		c += [x]
if len(b) == 0 and k % 2 == 1:
	c.reverse()
	for i in range(k):
		ans *= c[i]
		ans %= mod
	print(ans)
	exit()
b.reverse()
bi = 0
ci = 0
bl = len(b)
cl = len(c)
if k % 2 == 1:
	ans *= b[0]
	bi += 1
	k -= 1
while k > 0:
	if bl - 1 <= bi:
		ans *= c[ci] * c[ci + 1]
		ans %= mod
		ci += 2
	elif cl - 1 <= ci:
		ans *= b[bi] * b[bi + 1]
		ans %= mod
		bi += 2
	elif b[bi] * b[bi + 1] < c[ci] * c[ci + 1]:
		ans *= c[ci] * c[ci + 1]
		ans %= mod
		ci += 2
	else:
		ans *= b[bi] * b[bi + 1]
		ans %= mod
		bi += 2
	k -= 2
print(ans)


def solve():
	can_positive = False
	if len(P) > 0:
		if k < n:
			can_positive = True
		else:
			can_positive = len(M) % 2 == 0
	else:
		can_positive = k % 2 == 0
	if not can_positive:
		return sorted(P + M, key=lambda x: abs(x))[:k]
	P.sort()
	M.sort(reverse=True)
	a = [P.pop()] if k % 2 else [1]
	while len(P) >= 2:
		a.append(P.pop() * P.pop())
	while len(M) >= 2:
		a.append(M.pop() * M.pop())
	return a[:1] + sorted(a[1:], reverse=True)[:(k - k % 2) // 2]
(n, k) = map(int, input().split())
(P, M) = ([], [])
for a in map(int, input().split()):
	if a < 0:
		M.append(a)
	else:
		P.append(a)
(ans, mod) = (1, 10 ** 9 + 7)
for a in solve():
	ans *= a
	ans %= mod
print(ans)


import sys
from collections import deque
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, K, *A) = map(int, read().split())
	pos = [a for a in A if a >= 0]
	neg = [a for a in A if a < 0]
	pos.sort()
	neg.sort(reverse=True)
	if N == K:
		vec = A
	elif N == len(neg):
		if K & 1:
			vec = neg[:K]
		else:
			vec = neg[-K:]
	else:
		vec = []
		if K & 1:
			vec.append(pos.pop())
		tmp = []
		while len(neg) >= 2:
			tmp.append(neg.pop() * neg.pop())
		while len(pos) >= 2:
			tmp.append(pos.pop() * pos.pop())
		tmp.sort(reverse=True)
		vec.extend(tmp[:K // 2])
	ans = 1
	for a in vec:
		ans = ans * a % MOD
	print(ans)
	return
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
mod = 10 ** 9 + 7
l = 0
r = n - 1
ans = 1
if k % 2 == 1:
	ans = a[0]
	l = 1
if ans < 0:
	c = 1
	for i in range(k):
		c = c * a[i] % mod
	print(c)
else:
	for i in range(k // 2):
		L = a[l] * a[l + 1]
		R = a[r] * a[r - 1]
		if L >= R:
			ans = ans * L % mod
			l += 2
		else:
			ans = ans * R % mod
			r -= 2
	print(ans)


MOD = 10 ** 9 + 7

def modpow(a, n):
	r = 1
	while n > 0:
		if n % 2 == 1:
			r = r * a % MOD
		a = a * a % MOD
		n = n // 2
	return r
(N, K) = map(int, input().split())
As = list(map(int, input().split()))
As.sort(key=lambda x: abs(x), reverse=True)
As_srt = sorted(As)
if N == K or (As_srt[-1] < 0 and K % 2 == 1):
	ans = 1
	for i in range(K):
		ans *= As[N - i - 1]
		ans %= MOD
	print(ans)
else:
	ans = 1
	sign = 1
	for i in range(K):
		ans *= As[i]
		ans %= MOD
		if As[i] < 0:
			sign *= -1
	if sign < 0:
		rm_p = None
		rm_n = None
		for i in range(K):
			if rm_p != None and rm_n != None:
				break
			if rm_p == None and As[K - i - 1] > 0:
				rm_p = As[K - i - 1]
			if rm_n == None and As[K - i - 1] < 0:
				rm_n = As[K - i - 1]
		apd_zp = None
		apd_n = None
		for i in range(N - K):
			if apd_zp != None and apd_n != None:
				break
			if apd_zp == None and As[K + i] >= 0:
				apd_zp = As[K + i]
			if apd_n == None and As[K + i] < 0:
				apd_n = As[K + i]
		if rm_n == None or apd_zp == None:
			rm = rm_p
			apd = apd_n
		elif rm_p == None or apd_n == None:
			rm = rm_n
			apd = apd_zp
		elif abs(rm_p * apd_zp) <= abs(rm_n * apd_n):
			rm = rm_p
			apd = apd_n
		else:
			rm = rm_n
			apd = apd_zp
		ans *= apd
		ans %= MOD
		rm_inv = modpow(rm, MOD - 2)
		ans *= rm_inv
		ans %= MOD
	print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mod = int(1000000000.0 + 7)
AM = []
AP = []
AZC = 0
for a in A:
	if a < 0:
		AM.append(a)
	elif a == 0:
		AZC += 1
	else:
		AP.append(a)
if N - K < AZC:
	print(0)
	exit(0)
if N == K:
	wk = 1
	for a in A:
		wk *= a
		wk %= mod
	print(wk)
	exit(0)
if len(AP) == 0 and K % 2 == 1:
	if AZC > 0:
		print(0)
	else:
		wk = 1
		for i in range(K):
			wk *= AM[-1 - i]
			wk %= mod
		print(wk)
	exit(0)
wk = 1
if K % 2 == 1:
	wk *= AP.pop(-1)
	wk %= mod
K = K // 2
(mi, pi) = (0, 0)
AP = AP[::-1]
while K > 0:
	mwk = AM[mi] * AM[mi + 1] if mi + 1 < len(AM) else 0
	pwk = AP[pi] * AP[pi + 1] if pi + 1 < len(AP) else 0
	if mwk <= pwk:
		wk *= pwk % mod
		pi += 2
	else:
		wk *= mwk % mod
		mi += 2
	wk %= mod
	K -= 1
print(wk)


mod = 10 ** 9 + 7

def prod(A):
	r = 1
	for a in A:
		r *= abs(a)
		r %= mod
	return r
(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())), key=abs, reverse=True)
Ak = A[:K]
m = len([a for a in Ak if a < 0])
if m % 2 == 0:
	print(prod(Ak))
	exit()
r_p = [a for a in A[K:] if a >= 0]
r_n = [a for a in A[K:] if a <= 0]
a_p = [a for a in Ak if a > 0]
a_n_min = max([a for a in Ak if a < 0])
ans1 = ans2 = None
if r_p:
	v1 = abs(a_n_min)
	w1 = max(r_p)
	ans1 = prod(Ak) * pow(v1, mod - 2, mod) * w1 % mod
if a_p and r_n:
	v2 = min(a_p)
	w2 = abs(min(r_n))
	ans2 = prod(Ak) * pow(v2, mod - 2, mod) * w2 % mod
if ans1 and ans2:
	print(ans1 if w1 * v2 >= w2 * v1 else ans2)
	exit()
if ans1:
	print(ans1)
	exit()
if ans2:
	print(ans2)
	exit()
print(-prod(A[::-1][:K]) % mod)


(n, k) = [int(x) for x in input().strip().split(' ')]
p = 10 ** 9 + 7
num_list = [int(x) for x in input().strip().split(' ')]
num_list = sorted(num_list, reverse=True)
ans = 1
l_idx = 0
r_idx = -1
if num_list[0] < 0 and k % 2 == 1:
	for i in range(k):
		ans = ans * num_list[i] % p
else:
	while True:
		if k >= 2:
			l_prod = num_list[l_idx] * num_list[l_idx + 1]
			r_prod = num_list[r_idx] * num_list[r_idx - 1]
			if l_prod >= r_prod:
				ans = ans * num_list[l_idx] % p
				l_idx += 1
				k -= 1
			else:
				ans = ans * r_prod % p
				r_idx -= 2
				k -= 2
		elif k == 1:
			ans = ans * num_list[l_idx] % p
			ans %= p
			break
		else:
			break
print(ans)


from collections import defaultdict

def prod(A, k, mod):
	ans = 1
	for i in range(k):
		ans *= A[i]
		ans %= mod
	return ans

def solve():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	ans = 1
	if K == N:
		return prod(A, N, mod)
	minus = len([a for a in A if a < 0])
	if minus == N:
		if K % 2 == 0:
			A.sort()
		else:
			A.sort(reverse=True)
		return prod(A, K, mod)
	if K == 1:
		return max(A)
	A.sort(key=lambda x: -abs(x))
	if A[K] == 0:
		return 0
	minus = len([a for a in A[:K] if a < 0])
	flag = [1] * K + [0] * (N - K)
	d = defaultdict(lambda : -1)
	if minus % 2 == 1:
		for i in range(K, N):
			if A[i] >= 0:
				d['p2'] = i
				break
		for i in range(K, N):
			if A[i] < 0:
				d['m2'] = i
				break
		for i in range(K - 1, -1, -1):
			if A[i] > 0:
				d['p1'] = i
				break
		for i in range(K - 1, -1, -1):
			if A[i] < 0:
				d['m1'] = i
				break
		if d['p2'] == -1 or d['m1'] == -1:
			(flag[d['m2']], flag[d['p1']]) = (1, 0)
		elif d['m2'] == -1 or d['p1'] == -1:
			(flag[d['p2']], flag[d['m1']]) = (1, 0)
		elif A[d['p2']] * A[d['p1']] > A[d['m1']] * A[d['m2']]:
			(flag[d['p2']], flag[d['m1']]) = (1, 0)
		else:
			(flag[d['m2']], flag[d['p1']]) = (1, 0)
		ans = 1
		for i in range(N):
			if flag[i] == 1:
				ans *= A[i]
				ans %= mod
		return ans
	return prod(A, K, mod)
print(solve())


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
if n == k:
	ans = 1
	for q in a:
		ans *= q
		ans %= mod
	print(ans)
	exit()
if all((q >= 0 for q in a)):
	ans = 1
	a.sort()
	for _ in range(k):
		ans *= a.pop()
		ans %= mod
	print(ans)
	exit()
if all((q < 0 for q in a)):
	ans = 1
	a.sort()
	if k % 2 == 0:
		for i in range(k):
			ans *= a[i]
			ans %= mod
	else:
		for _ in range(k):
			ans *= a.pop()
			ans %= mod
	print(ans)
	exit()
pos = []
neg = []
for q in a:
	if q >= 0:
		pos.append(q)
	else:
		neg.append(q)
pos.sort()
neg.sort()
neg = neg[::-1]
kk = k
if kk % 2 == 1:
	ans = pos.pop() % mod
	kk = kk - 1
else:
	ans = 1
while kk > 0:
	if len(pos) < 2:
		ans = ans * neg.pop() % mod * neg.pop() % mod
		kk -= 2
	elif len(neg) < 2:
		ans = ans * pos.pop() % mod * pos.pop() % mod
		kk -= 2
	elif pos[-1] * pos[-2] >= neg[-1] * neg[-2]:
		ans = ans * pos.pop() % mod * pos.pop() % mod
		kk -= 2
	else:
		ans = ans * neg.pop() % mod * neg.pop() % mod
		kk -= 2
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
(a, b, i) = (0, 1, 0)
mod = 10 ** 9 + 7
ans = 1
while i < K - 1:
	if A[a] * A[a + 1] > A[-b] * A[-b - 1]:
		ans *= A[a] * A[a + 1]
		ans %= mod
		a += 2
		i += 2
	else:
		ans *= A[-b]
		ans %= mod
		b += 1
		i += 1
if i == K - 1:
	ans *= A[-b]
	ans %= mod
if A[-1] < 0 and K % 2 == 1:
	ans = 1
	for i in A[N - K:]:
		ans *= i
		ans %= mod
print(ans % mod)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
(p, n) = ([], [])
for Ai in A:
	if Ai >= 0:
		p.append(Ai)
	else:
		n.append(Ai)
if len(n) == N and K % 2 == 1:
	n.sort(reverse=True)
	ans = 1
	for ni in n[:K]:
		ans *= ni
		ans %= MOD
	print(ans)
	exit()
if K == N and len(n) % 2 == 1:
	ans = 1
	for Ai in A:
		ans *= Ai
		ans %= MOD
	print(ans)
	exit()
p.sort(reverse=True)
n.sort()
l = []
if K % 2 == 1:
	ans = p[0]
	p = p[1:]
else:
	ans = 1
for i in range(len(p) // 2):
	l.append(p[2 * i] * p[2 * i + 1])
for i in range(len(n) // 2):
	l.append(n[2 * i] * n[2 * i + 1])
l.sort(reverse=True)
for li in l[:K // 2]:
	ans *= li
	ans %= MOD
print(ans)


MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
if N == K:
	ans = 1
	for i in range(0, N, 1):
		ans = ans * A[i] % MOD
	print(ans)
	exit()
plus = []
minus = []
for i in range(0, N, 1):
	if A[i] < 0:
		minus.append(-A[i])
	if A[i] > 0:
		plus.append(A[i])
	if A[i] == 0:
		minus.append(0)
		plus.append(0)
if len(plus) == 0 and K % 2 == 1:
	minus.sort()
	ans = 1
	for i in range(0, K, 1):
		ans = ans * -minus[i] % MOD
	print(ans)
	exit()
plus.sort(reverse=True)
minus.sort(reverse=True)
ans = 1
if K % 2 == 1:
	ans = ans * plus[0]
	plus.pop(0)
pairs = []
for i in range(1, len(plus), 2):
	pairs.append(plus[i] * plus[i - 1])
for i in range(1, len(minus), 2):
	pairs.append(minus[i] * minus[i - 1])
pairs.sort(reverse=True)
for i in range(0, K // 2, 1):
	ans = ans * pairs[i] % MOD
print(ans)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
count = k
(B, C) = ([], [])
for i in A:
	if i <= 0:
		B.append(i)
	else:
		C.append(i)
B.sort(key=lambda x: abs(x))
C.sort()
(ans, flag) = (1, 1)
while k != 0:
	if k >= 2:
		if len(B) >= 2 and len(C) >= 2:
			if B[-1] * B[-2] > C[-1] * C[-2]:
				ans *= B.pop() * B.pop()
				k -= 2
			else:
				ans *= C.pop()
				k -= 1
		elif len(B) >= 2:
			ans *= B.pop() * B.pop()
			k -= 2
		elif len(C) >= 2:
			ans *= C.pop() * C.pop()
			k -= 2
		else:
			flag = 0
			break
	elif len(C) > 0:
		ans *= C.pop()
		k -= 1
	else:
		flag = 0
		break
	ans %= mod
if flag:
	print(ans)
else:
	ans = 1
	A.sort(reverse=True)
	for i in range(count):
		ans *= A[i]
		ans %= mod
	print(ans)


def solve(ls, k, debug=0):
	modulo = 10 ** 9 + 7
	n = len(ls)
	n_neg = 0
	for i in range(n):
		n_neg += ls[i] < 0
	n_pos = n - n_neg
	ls_abs = [abs(x) for x in ls]
	ls_abs_argsort = sorted(list(range(n)), key=lambda i: -ls_abs[i])
	if n_neg >= k:
		positive = k % 2 == 0 or n_pos > 0
	else:
		positive = n_neg % 2 == 0 or n > k
	if not positive:
		p = 1
		for i in range(k):
			x = ls[ls_abs_argsort[-1 - i]]
			p *= x
			p %= modulo
		return p
	s = 1
	for i in range(k):
		x = ls[ls_abs_argsort[i]]
		s *= -1 if x < 0 else 1
	if s > 0:
		p = 1
		for i in range(k):
			x = ls[ls_abs_argsort[i]]
			p *= x
			p %= modulo
		return p
	opt1 = None
	opt2 = None
	neg1 = pos1 = None
	pos2 = neg2 = None
	swap_pos = None
	for i in range(k, n):
		if ls[ls_abs_argsort[i]] >= 0:
			swap_pos = i
			pos1 = ls[ls_abs_argsort[i]]
			break
	swap_neg = None
	for i in range(k)[::-1]:
		if ls[ls_abs_argsort[i]] < 0:
			swap_neg = i
			neg1 = ls[ls_abs_argsort[i]]
			break
	if swap_pos is not None and swap_neg is not None:
		p = 1
		p *= ls[ls_abs_argsort[swap_pos]]
		p %= modulo
		for i in range(k):
			if i == swap_neg:
				continue
			x = ls[ls_abs_argsort[i]]
			p *= x
			p %= modulo
		opt1 = p
	swap_pos = None
	for i in range(k)[::-1]:
		if ls[ls_abs_argsort[i]] >= 0:
			swap_pos = i
			pos2 = ls[ls_abs_argsort[i]]
			break
	swap_neg = None
	for i in range(k, n):
		if ls[ls_abs_argsort[i]] < 0:
			swap_neg = i
			neg2 = ls[ls_abs_argsort[i]]
			break
	if swap_pos is not None and swap_neg is not None:
		p = 1
		p *= ls[ls_abs_argsort[swap_neg]]
		p %= modulo
		for i in range(k):
			if i == swap_pos:
				continue
			x = ls[ls_abs_argsort[i]]
			p *= x
			p %= modulo
			opt2 = p
	if opt1 is None:
		return opt2
	if opt2 is None:
		return opt1
	if pos1 * pos2 > neg1 * neg2:
		return opt1
	return opt2

def main(istr, ostr):
	(n, k) = list(map(int, istr.readline().strip().split()))
	ls = list(map(int, istr.readline().strip().split()))
	result = solve(ls, k)
	print(result, file=ostr)

def __starting_point():
	import sys
	main(sys.stdin, sys.stdout)
__starting_point()


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
AA = sorted(A, key=lambda x: -abs(x))
nega1 = []
posi1 = []
for a in AA[:k]:
	if a < 0:
		nega1.append(a)
	else:
		posi1.append(a)
nega2 = []
posi2 = []
for a in AA[k:]:
	if a < 0:
		nega2.append(a)
	else:
		posi2.append(a)
if all((a < 0 for a in A)) and k % 2 == 1:
	AA = sorted(A, key=lambda x: abs(x))
	nega1 = []
	posi1 = []
	for a in AA[:k]:
		nega1.append(a)
elif n == k:
	pass
elif len(nega1) % 2 != 0:
	if posi1 and nega2 and posi2:
		if abs(nega1[-1] * nega2[0]) < abs(posi1[-1] * posi2[0]):
			del nega1[-1]
			nega1.append(posi2[0])
		else:
			del posi1[-1]
			posi1.append(nega2[0])
	elif not posi1 or not nega2:
		del nega1[-1]
		nega1.append(posi2[0])
	elif not posi2:
		del posi1[-1]
		posi1.append(nega2[0])
a = 1
for m in posi1:
	a = a * m % MOD
for p in nega1:
	a = a * p % MOD
print(a)


def myabs(n):
	n = int(n)
	if n > 0:
		return [n, 1]
	else:
		return [abs(n), -1]
(N, K) = map(int, input().split())
A = list(map(myabs, input().split()))
A.sort(reverse=True)
Mod = 10 ** 9 + 7

def main(n, k, a, mod):
	flag = True
	for i in a:
		if i[1] == 1:
			flag = False
			break
	if k % 2 == 0:
		flag = False
	if flag:
		ans = 1
		for i in range(n - 1, n - 1 - k, -1):
			ans *= a[i][0] * -1 % mod
			ans %= mod
		print(ans)
	else:
		ans = [1, 1]
		neg_flag = False
		min_neg = -1
		min_pos = -1
		for i in range(k):
			if a[i][1] == -1:
				if neg_flag == True:
					neg_flag = False
					ans[1] *= a[i][0]
					ans[0] = ans[1]
				else:
					neg_flag = True
					ans[1] *= a[i][0]
					min_neg = i
			else:
				ans[0] *= a[i][0]
				ans[1] *= a[i][0]
				min_pos = i
			ans[0] %= mod
			ans[1] %= mod
		if neg_flag and n != k:
			next_pos = -1
			next_neg = -1
			for i in range(k, n):
				if next_pos == -1 and a[i][1] == 1:
					next_pos = a[i][0]
				elif next_neg == -1 and a[i][1] == -1:
					next_neg = a[i][0]
				if next_pos >= 0 and next_neg >= 0:
					break
			if min_pos == -1:
				ans[0] *= next_pos % mod
				ans[0] %= mod
				print(ans[0])
			elif a[min_neg][0] * next_neg > a[min_pos][0] * next_pos:
				fin_ans = 1
				for i in range(k):
					if i != min_pos:
						fin_ans *= a[i][0] % mod
						fin_ans %= mod
				fin_ans *= next_neg % mod
				fin_ans %= mod
				print(fin_ans)
			else:
				fin_ans = 1
				for i in range(k):
					if i != min_neg:
						fin_ans *= a[i][0] % mod
						fin_ans %= mod
				fin_ans *= next_pos % mod
				fin_ans %= mod
				print(fin_ans)
		elif n == k and neg_flag:
			print(ans[1] * -1 % mod)
		else:
			print(ans[1])

def __starting_point():
	main(N, K, A, Mod)
__starting_point()


(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
ans = 1
mi = []
pl = []
for a in A:
	if a < 0:
		mi.append(a)
	else:
		pl.append(a)
if N == K:
	for a in A:
		ans *= a
		ans %= mod
	print(ans)
	exit()
if pl == []:
	if K % 2:
		for k in range(K):
			ans *= mi[-1 - k]
			ans %= mod
	else:
		for k in range(K):
			ans *= mi[k]
			ans %= mod
	print(ans)
	exit()
pl = pl[::-1]
ip = 0
im = 0
if K % 2:
	ans = pl[0]
	ip += 1
	K -= 1
while K > 0:
	check = True
	if ip + 2 <= len(pl):
		x = pl[ip] * pl[ip + 1]
	else:
		x = 1
	if im + 2 <= len(mi):
		y = mi[im] * mi[im + 1]
	else:
		check = False
		y = 1
	if x >= y or check == False:
		ans *= x
		ans %= mod
		ip += 2
	else:
		ans *= y
		ans %= mod
		im += 2
	K -= 2
print(ans)


def resolve():
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	MOD = 10 ** 9 + 7
	ans = 1
	if k == 1:
		ans = a[-1]
	elif a[0] >= 0 or (a[-1] < 0 and k % 2 == 1):
		for i in a[-k:]:
			ans = ans * i % MOD
	elif a[-1] < 0 and k % 2 == 0:
		for i in a[:k]:
			ans = ans * i % MOD
	else:
		ans = 1
		if k % 2 == 1 and n >= 3:
			ans *= a[-1]
			ans %= MOD
			(l, r) = (0, -2)
			lm = a[0] * a[1]
			rm = a[-2] * a[-3]
		else:
			(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
	print(ans)
resolve()


(n, k) = map(int, input().split())
(*a,) = map(int, input().split())
ans = 1
mod = 10 ** 9 + 7
a.sort()
if a[0] >= 0:
	for i in range(n - 1, n - k - 1, -1):
		ans *= a[i]
		ans %= mod
	print(ans)
	exit()
if a[-1] <= 0:
	if k % 2:
		for i in range(n - 1, n - k - 1, -1):
			ans *= a[i]
			ans %= mod
	else:
		for i in range(k):
			ans *= a[i]
			ans %= mod
	print(ans)
	exit()
l = 0
r = n - 1
if k % 2:
	ans = a[-1]
	r -= 1
	k -= 1
while k:
	if a[l] * a[l + 1] > a[r] * a[r - 1]:
		ans *= a[l] * a[l + 1]
		l += 2
	else:
		ans *= a[r] * a[r - 1]
		r -= 2
	k -= 2
	ans %= mod
print(ans)


from collections import deque
div = 10 ** 9 + 7
(n, k) = map(int, input().split())
A = deque(sorted([int(x) for x in input().split()]))
maxA = A[-1]
ans = 1
for i in range(k // 2):
	l1 = A[0]
	l2 = A[1]
	r1 = A[-1]
	r2 = A[-2]
	l = l1 * l2
	r = r1 * r2
	if k % 2 == 1 and maxA < 0:
		ans *= r
		ans %= div
		A.pop()
		A.pop()
	elif l < r:
		ans *= r
		ans %= div
		A.pop()
		A.pop()
	else:
		ans *= l
		ans %= div
		A.popleft()
		A.popleft()
if k % 2 == 1:
	ans *= A[-1]
	ans %= div
print(ans)


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
index_change = 0
ans = 1
for i in range(n - 1):
	if a[i] <= 0 and a[i + 1] > 0:
		index_change = i + 1
		break
else:
	if k % 2 == 1:
		for i in range(1, k + 1):
			ans *= a[-i]
			ans %= mod
	else:
		for i in range(k):
			ans *= a[i]
			ans %= mod
	print(ans)
	exit()
l = 0
r = n - 1
while k > 0:
	if k == 1:
		if r >= index_change:
			ans *= a[r]
			ans %= mod
			break
		else:
			ans *= a[l] * a[l + 1]
			ans %= mod
			ans *= pow(a[r + 1], mod - 2, mod)
			ans %= mod
			break
	else:
		left = a[l] * a[l + 1]
		right = a[r] * a[r - 1]
		if left >= right:
			ans *= left
			ans %= mod
			l += 2
			k -= 2
		else:
			ans *= a[r]
			ans %= mod
			r -= 1
			k -= 1
print(ans)


import sys
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
MOD = 10 ** 9 + 7
plus = []
minus = []
zero = []
for i in range(n):
	if a[i] > 0:
		plus.append(a[i])
	if a[i] < 0:
		minus.append(a[i])
	if a[i] == 0:
		zero.append(a[i])
if k == n:
	ans = 1
	for i in range(k):
		ans = ans * a[i] % MOD
	print(ans)
	sys.exit()
if len(plus) == 0:
	if k % 2 != 0:
		a.reverse()
	ans = 1
	for i in range(k):
		ans = ans * a[i] % MOD
	print(ans)
	sys.exit()
if len(plus) + len(minus) < k:
	print(0)
	sys.exit()
m = len(minus)
minus.sort()
plus.reverse()
plpointer = k
if k > len(plus):
	plpointer = 2 * (len(plus) // 2)
	if k % 2 == 1:
		if plpointer + 1 <= len(plus):
			plpointer += 1
		else:
			plpointer -= 1
mnpointer = k - plpointer
while mnpointer < m - 1 and plpointer >= 2 and (minus[mnpointer] * minus[mnpointer + 1] > plus[plpointer - 1] * plus[plpointer - 2]):
	mnpointer += 2
	plpointer -= 2
ans = 1
for i in range(mnpointer):
	ans = ans * minus[i] % MOD
for i in range(plpointer):
	ans = ans * plus[i] % MOD
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
res = 1
a.sort(reverse=True)
if a[0] < 0 and k % 2 == 1:
	for i in range(k):
		res = res * a[i] % mod
else:
	right = n - 1
	left = 0
	while k > 1:
		if a[right] * a[right - 1] < a[left] * a[left + 1]:
			res = res * a[left] % mod
			left += 1
			k -= 1
		else:
			res = res * a[right] * a[right - 1] % mod
			right -= 2
			k -= 2
	if k == 1:
		res = res * a[left] % mod
print(res)


(n, k, *a) = map(int, open(0).read().split())
a.sort()
mod = 10 ** 9 + 7
ans = 1
i = 0
j = -1
kk = k
while kk > 1:
	if a[i] * a[i + 1] > a[j] * a[j - 1]:
		ans = ans * a[i] * a[i + 1] % mod
		i += 2
		kk -= 2
	else:
		ans = ans * a[j] % mod
		j -= 1
		kk -= 1
if kk == 1:
	ans = ans * a[j] % mod
if a[-1] < 0 and k % 2 == 1:
	ans = 1
	for i in a[n - k:]:
		ans = ans * i % mod
print(ans)


mod = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 1
left = 0
right = len(A) - 1
if A[0] < 0 and K % 2 == 1:
	for i in range(K):
		ans = ans * A[i] % mod
elif K % 2 == 0:
	while K > 0:
		r = A[right] * A[right - 1]
		l = A[left] * A[left + 1]
		if l > r:
			ans = ans * l % mod
			left += 2
		else:
			ans = ans * r % mod
			right -= 2
		K -= 2
else:
	p = A.pop(0)
	K -= 1
	right -= 1
	while K > 0:
		r = A[right] * A[right - 1]
		l = A[left] * A[left + 1]
		if l > r:
			ans = ans * l % mod
			left += 2
		else:
			ans = ans * r % mod
			right -= 2
		K -= 2
	ans = ans * p % mod
while ans < 0:
	ans = ans + mod
print(ans)


import sys
from collections import deque
import bisect

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

def main():
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	A.sort()
	pp = int(bisect.bisect_left(A, 0))
	A_minus = deque(A[:pp])
	A_plus = deque(A[pp:])
	AA = deque([])
	AAm = deque([])
	if N == K:
		ans = 1
		for i in A:
			ans *= i
			ans %= mod
		print(ans % mod)
	elif K % 2 == 0:
		ans = 1
		while len(A_minus) >= 2:
			a1 = A_minus.popleft()
			a2 = A_minus.popleft()
			AAm.append(a1 * a2)
		while len(A_plus) >= 2:
			a1 = A_plus.pop()
			a2 = A_plus.pop()
			AA.append(a1 * a2)
		for i in range(K // 2):
			if len(AAm) == 0:
				temp = AA.popleft()
			elif len(AA) == 0:
				temp = AAm.popleft()
			elif AAm[0] > AA[0]:
				temp = AAm.popleft()
			else:
				temp = AA.popleft()
			ans *= temp
			ans %= mod
		print(ans % mod)
	elif len(A_plus) == 0:
		ans = 1
		for i in range(K):
			ans *= A_minus.pop()
			ans %= mod
		print(ans % mod)
	else:
		ans = A_plus.pop()
		while len(A_minus) >= 2:
			a1 = A_minus.popleft()
			a2 = A_minus.popleft()
			AAm.append(a1 * a2)
		while len(A_plus) >= 2:
			a1 = A_plus.pop()
			a2 = A_plus.pop()
			AA.append(a1 * a2)
		for i in range(K // 2):
			if len(AAm) == 0:
				temp = AA.popleft()
			elif len(AA) == 0:
				temp = AAm.popleft()
			elif AAm[0] > AA[0]:
				temp = AAm.popleft()
			else:
				temp = AA.popleft()
			ans *= temp
			ans %= mod
		print(ans % mod)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
c = []
d = 1
m = 10 ** 9 + 7
for i in range(n):
	if a[i] < 0:
		c.append(a[i])
	else:
		b.append(a[i])
b.sort()
c.sort(reverse=True)
if len(b) == 0 and k % 2 == 1:
	for i in range(k):
		d = d * c[i] % m
else:
	while k > 0:
		if len(b) > 1 and len(c) > 1:
			if b[-1] * b[-2] < c[-1] * c[-2] and k > 1:
				d = d * c.pop() % m
				d = d * c.pop() % m
				k -= 2
			else:
				d = d * b.pop() % m
				k -= 1
		elif len(b) == 1 and len(c) > 1:
			if k > 1:
				d = d * c.pop() % m
				d = d * c.pop() % m
				k -= 2
			else:
				d = d * b.pop() % m
				k -= 1
		elif len(b) >= 1 and len(c) <= 1:
			d = d * b.pop() % m
			k -= 1
		else:
			d = d * c.pop() % m
			k -= 1
print(d)


import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
	(n, k) = map(int, readline().split())
	A = list(map(int, readline().split()))
	MOD = int(1000000000.0) + 7
	A.sort()
	ans = 1
	if A[n - 1] == 0 and k & 1:
		ans = 0
	elif A[n - 1] <= 0 and k & 1:
		for i in range(n - 1, n - k - 1, -1):
			ans = ans * A[i] % MOD
	else:
		i = 0
		j = n - 1
		if k & 1:
			ans = ans * A[j] % MOD
			j -= 1
			k -= 1
		k >>= 1
		for itr in range(k):
			left_product = A[i] * A[i + 1]
			right_product = A[j] * A[j - 1]
			if left_product > right_product:
				ans = ans * left_product % MOD
				i += 2
			else:
				ans = ans * right_product % MOD
				j -= 2
	print(ans % MOD)
main()


from collections import deque
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
mod = pow(10, 9) + 7
A.sort(reverse=True)
deque = deque()
for a in A:
	deque.append(a)
ans = 1
cnt = 0
if K % 2 == 1:
	ans *= deque.popleft()
	cnt += 1
if ans <= 0:
	for i in range(K - 1):
		ans *= deque.popleft()
		ans %= mod
else:
	while cnt < K:
		x1 = deque.popleft()
		x2 = deque.popleft()
		deque.appendleft(x2)
		deque.appendleft(x1)
		y1 = deque.pop()
		y2 = deque.pop()
		if x1 * x2 < y1 * y2:
			ans *= y1 * y2
			ans %= mod
			cnt += 2
		else:
			ans *= x1 * x2
			ans %= mod
			if deque:
				x1 = deque.popleft()
			if deque:
				x2 = deque.popleft()
			deque.append(y2)
			deque.append(y1)
			cnt += 2
print(ans)


MOD = int(1000000000.0 + 7)

def power(a, n):
	if a == 0:
		return 0
	if n == 0:
		return 1
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * a % MOD
		a = a * a % MOD
		n //= 2
	return res

def inverse(n):
	return power(n, MOD - 2)
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = []
(pos, neg) = (0, 0)
for a in A:
	if a > 0:
		B.append([a, 1])
		pos += 1
	if a < 0:
		B.append([-a, -1])
		neg += 1
	if a == 0:
		B.append([0, 0])
B.sort(reverse=True)
(ans, sign) = (1, 1)
if N == neg and K % 2 == 1:
	for i in range(K):
		ans *= B[N - 1 - i][0]
		ans %= MOD
	print(-ans % MOD)
	return
for i in range(K):
	ans *= B[i][0]
	ans %= MOD
	sign *= B[i][1]
if N == K:
	if sign >= 0:
		print(ans)
	else:
		print(-ans % MOD)
	return
if sign < 0:
	(out_neg, out_pos) = (0, 0)
	(in_pos, in_neg) = (0, 0)
	for i in range(K):
		if B[K - 1 - i][1] < 0:
			out_neg = B[K - 1 - i][0]
			break
	for i in range(K):
		if B[K - 1 - i][1] > 0:
			out_pos = B[K - 1 - i][0]
			break
	for i in range(N - K):
		if B[K + i][1] > 0:
			in_pos = B[K + i][0]
			break
	for i in range(N - K):
		if B[K + i][1] < 0:
			in_neg = B[K + i][0]
			break
	if in_neg == 0 or out_pos == 0:
		ans = ans * in_pos % MOD * inverse(out_neg) % MOD
	elif in_pos == 0 or out_neg == 0:
		ans = ans * in_neg % MOD * inverse(out_pos) % MOD
	elif out_pos * in_pos < out_neg * in_neg:
		ans = ans * in_neg % MOD * inverse(out_pos) % MOD
	else:
		ans = ans * in_pos % MOD * inverse(out_neg) % MOD
print(ans)


def solve():
	can_positive = False
	if len(p) > 0:
		if k < n:
			can_positive = True
		else:
			can_positive = len(m) % 2 == 0
	else:
		can_positive = k % 2 == 0
	if not can_positive:
		m.sort(reverse=True)
		return m[:k] + p
	p.sort()
	m.sort(reverse=True)
	a = [p.pop()] if k % 2 else [1]
	while len(p) >= 2:
		a.append(p.pop() * p.pop())
	while len(m) >= 2:
		a.append(m.pop() * m.pop())
	return a[:1] + sorted(a[1:], reverse=True)[:(k - k % 2) // 2]
mod = 10 ** 9 + 7
(n, k) = list(map(int, input().split()))
(m, p) = ([], [])
for i in map(int, input().split()):
	if i < 0:
		m.append(i)
	else:
		p.append(i)
ans = 1
for i in solve():
	ans = ans * i % mod
print(ans)


from bisect import bisect_left, bisect_right
p = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(list(map(int, input().split())))
pi = 1
ni = 0
ans = 1
i = 0
while i < k - 1:
	if a[ni] * a[ni + 1] > a[-pi] * a[-pi - 1]:
		ans = ans * a[ni] * a[ni + 1] % p
		ni += 2
		i += 2
	else:
		ans = ans * a[-pi] % p
		pi += 1
		i += 1
if i == k - 1:
	ans = ans * a[-pi] % p
if a[-1] < 0 and k % 2 == 1:
	ans = 1
	for i in a[n - k:]:
		ans = ans * i % p
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
if max(a) < 0:
	a.sort()
	ans = 1
	if k % 2 == 0:
		for e in a[:k]:
			ans *= e
			ans %= mod
	else:
		for e in a[-k:]:
			ans *= e
			ans %= mod
	print(ans)
elif k == n:
	ans = 1
	for e in a:
		ans *= e
		ans %= mod
	print(ans)
else:
	neg = []
	pos = []
	for e in a:
		if e < 0:
			neg.append(e)
		else:
			pos.append(e)
	neg.sort()
	pos.sort(reverse=True)
	ans = 1
	if k % 2:
		ans *= pos.pop(0)
		k -= 1
	nums = [e1 * e2 for (e1, e2) in zip(neg[::2], neg[1::2])]
	nums += [e1 * e2 for (e1, e2) in zip(pos[::2], pos[1::2])]
	nums.sort(reverse=True)
	for e in nums[:k // 2]:
		ans *= e
		ans %= mod
	print(ans)


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if max(a) < 0:
	if k % 2:
		a.sort(reverse=1)
	else:
		a.sort()
	ans = 1
	for i in a[:k]:
		ans = ans * i % mod
	exit(print(ans))
if n == k:
	ans = 1
	for i in a:
		ans = ans * i % mod
	exit(print(ans))
p = [(0, 0)]
m = [(0, 0)]
for i in a:
	if i < 0:
		m.append((-i, 1))
	else:
		p.append((i, 0))
pp = mm = None
p.sort()
m.sort()
oe = 0
ans = 1
for i in range(k):
	if p[-1][0] > m[-1][0]:
		(t, f) = p.pop()
		pp = t
	else:
		(t, f) = m.pop()
		mm = t
	ans = ans * t % mod
	if ans == 0:
		exit(print(0))
	oe ^= f
if oe:
	if mm == None:
		ans = ans * pow(pp, mod - 2, mod) * m[-1][0] % mod
	elif pp == None:
		ans = ans * pow(mm, mod - 2, mod) * p[-1][0] % mod
	elif pp * p[-1][0] > mm * m[-1][0]:
		ans = ans * pow(mm, mod - 2, mod) * p[-1][0] % mod
	else:
		ans = ans * pow(pp, mod - 2, mod) * m[-1][0] % mod
print(ans)


from functools import reduce
mod = 10 ** 9 + 7
(n, k, *a) = list(map(int, open(0).read().split()))
a.sort(key=lambda x: abs(x))
ans = reduce(lambda a, b: a * b % mod, a[-k:])
c = a[-k:]
j = sum((i < 0 for i in c)) % 2
if j:
	c = a[-k:]
	neg = [i for i in c if i < 0]
	pos = [i for i in c if i > 0]
	b = sorted(a[:n - k])
	if b == []:
		print(ans)
		return
	if neg == []:
		if pos[0] * b[0] < 0:
			ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
		else:
			ans = reduce(lambda a, b: a * b % mod, a[:k])
	elif pos == []:
		if neg[0] * b[-1] < 0:
			ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
		else:
			ans = reduce(lambda a, b: a * b % mod, a[:k])
	elif pos[0] * b[-1] < neg[0] * b[0] and pos[0] * b[0] < 0:
		ans = ans * pow(pos[0], mod - 2, mod) * b[0] % mod
	elif 0 > b[-1] * neg[0]:
		ans = ans * pow(neg[0], mod - 2, mod) * b[-1] % mod
	else:
		ans = reduce(lambda a, b: a * b % mod, a[:k])
print(ans)


from collections import deque
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
d = deque(A)
import time
l = []
if K % 2 == 0 or (K % 2 == 1 and A[0] >= 0):
	for i in range(K // 2):
		if d[0] * d[1] > d[-1] * d[-2] and (i == K // 2 - 1 or (len(d) > 2 and d[2] > 0)):
			l.append(d.popleft())
			l.append(d.popleft())
		else:
			l.append(d.pop())
			l.append(d.pop())
	if K % 2 == 1:
		l.append(d[0])
else:
	for i in range(K):
		l.append(d.popleft())
ans = 1
for i in l:
	ans *= i
	ans %= 10 ** 9 + 7
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
a.sort()
if a[-1] <= 0:
	if k % 2 == 0:
		ans = 1
		for i in range(k):
			ans *= a[i]
			ans %= mod
		print(ans % mod)
	else:
		ans = 1
		for i in range(k):
			ans *= a[-1 - i]
			ans %= mod
		print(ans % mod)
elif a[0] >= 0:
	ans = 1
	for i in range(k):
		ans *= a[-1 - i]
		ans %= mod
	print(ans % mod)
else:
	from collections import deque
	a = deque(a)
	ans = 1
	while k:
		if k == 1:
			ans *= a.pop()
			ans %= mod
			k -= 1
		elif a[0] * a[1] >= a[-1] * a[-2]:
			ans *= a.popleft()
			ans *= a.popleft()
			ans %= mod
			k -= 2
		else:
			ans *= a.pop()
			ans *= a.pop()
			ans %= mod
			k -= 2
	print(ans)


from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter, defaultdict
from operator import mul
import copy
import heapq
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 18
import bisect
import statistics
mod = 10 ** 9 + 7
(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
import numpy as np
x = np.argsort(list([-abs(x) for x in A]))
B = []
C = []
for xx in x:
	B.append(A[xx])
	C.append(np.sign(A[xx]))
ans = 1
s = 1
flag4 = 0
for i in range(K):
	s *= C[i]
if s < 0:
	p = np.sign(B[K - 1])
	flag1 = 0
	for i in range(K - 1, -1, -1):
		if C[i] == p * -1:
			idx1 = i
			flag1 = 1
			break
	flag2 = 0
	for i in range(K, N):
		if C[i] == p * -1:
			idx2 = i
			flag2 = 1
			break
	flag3 = 0
	if flag1 == 1:
		for i in range(K, N):
			if C[i] == p:
				idx3 = i
				flag3 = 1
				break
	if flag1 and flag2 and flag3:
		if abs(B[K - 1]) * abs(B[idx3]) <= abs(B[idx1]) * abs(B[idx2]):
			B[K - 1] = B[idx2]
		else:
			B[idx1] = B[idx3]
	elif flag1 and (not flag2) and flag3:
		B[idx1] = B[idx3]
	elif flag1 and flag2 and (not flag3):
		B[K - 1] = B[idx2]
	elif not flag1 and flag2:
		B[K - 1] = B[idx2]
	else:
		flag4 = 1
if flag4:
	for i in range(N - 1, N - K - 1, -1):
		ans = ans * (B[i] % mod) % mod
else:
	for i in range(K):
		ans = ans * (B[i] % mod) % mod
print(ans % mod)


(n, k) = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10 ** 9 + 7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
	for i in range(k):
		ans *= a_list[n - 1 - i]
		ans %= mod
else:
	l = 0
	r = -1
	mlt1 = a_list[0] * a_list[1]
	mlt2 = a_list[-2] * a_list[-1]
	count = 0
	while True:
		if count == k:
			break
		elif count == k - 1:
			ans *= a_list[r] % mod
			ans %= mod
			break
		if mlt1 >= mlt2:
			ans *= mlt1 % mod
			l += 2
			count += 2
			if l <= n - 2:
				mlt1 = a_list[l + 1] * a_list[l]
		else:
			ans *= a_list[r] % mod
			r -= 1
			count += 1
			if r >= -n + 1:
				mlt2 = a_list[r - 1] * a_list[r]
		ans %= mod
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
(m, p, z) = ([], [], 0)
for a in A:
	if a < 0:
		m.append(a)
	elif a > 0:
		p.append(a)
	else:
		z += 1
m.sort()
p.sort()
mod = 10 ** 9 + 7
from functools import reduce
if (len(p) or K % 2 == 0) and K < len(m) + len(p) or (K == len(m) + len(p) and len(m) % 2 == 0):
	r = 1
	(i, j) = (0, 0)
	while i + j < K:
		if i < len(m) - 1 and i + j < K - 1 and (j >= len(p) - 1 or m[i] * m[i + 1] > p[-j - 1] * p[-j - 2]):
			r = r * m[i] * m[i + 1] % mod
			i += 2
		else:
			r = r * p[-j - 1] % mod
			j += 1
	print(r)
elif z:
	print(0)
else:
	print(reduce(lambda x, y: x * y % mod, (m + p)[-K:]))


import sys
input = sys.stdin.readline

def main():
	(n, k) = map(int, input().split())
	A = sorted(map(int, input().split()))
	mod = 10 ** 9 + 7
	(ans, sign) = (1, 1)
	(l, r) = (0, n - 1)
	if k % 2:
		ans = A[r]
		r -= 1
		k -= 1
		if ans < 0:
			sign = -1
	while k:
		x = A[l] * A[l + 1]
		y = A[r] * A[r - 1]
		if x * sign > y * sign:
			ans = x % mod * ans % mod
			l += 2
		else:
			ans = y % mod * ans % mod
			r -= 2
		k -= 2
	print((ans + mod) % mod)
main()