Problem:
 Score : 500 points    Problem Statement 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 1 4 2
1 2 -3 -4      Sample Output 1 12  The possible products of the two chosen elements are 2 , -3 , -4 , -6 , -8 , and 12 , so the maximum product is 12 .       Sample Input 2 4 3
-1 -2 -3 -4      Sample Output 2 1000000001  The possible products of the three chosen elements are -24 , -12 , -8 , and -6 , so the maximum product is -6 .  We print this value modulo (10^9+7) , that is, 1000000001 .       Sample Input 3 2 1
-1 1000000000      Sample Output 3 1000000000  The possible products of the one chosen element are -1 and 1000000000 , so the maximum product is 1000000000 .       Sample Input 4 10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1      Sample Output 4 999983200  Be sure to print the product modulo (10^9+7) .

Solution (Python):
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))

if N==K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
elif A[K-1]==0:
    ans = 0
else:
    p = []
    p_ = []
    n = []
    n_ = []
    for i in range(N):
        a = A[i]
        if i<K:
            if a>0:
                p.append(a)
            elif a<0:
                n.append(a)
        else:
            if a>0:
                p_.append(a)
            elif a<0:
                n_.append(a)
    if len(n)%2==0:
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
        for a in p:
            ans *= a
            ans %= mod
    else:
        if len(p)+len(p_)==0:
            if len(n)+len(n_)==N:
                n += n_
                ans = 1
                for i in range(K):
                    ans *= n[-i-1]
                    ans %= mod
            else:
                ans = 0
        else:
            if len(p)==0:
                n.pop()
                ans = p_[0]
                for a in n:
                    ans *= a
                    ans %= mod
            else:
                cand = []
                ap = p.pop()
                if p_:
                    cand.append([ap,p_[0]])
                an = n.pop()
                if n_:
                    cand.append([an,n_[0]])
                if len(cand)==2:
                    ap1,ap2 = cand[0]
                    an1,an2 = cand[1]
                    ans = max(ap1*ap2,an1*an2)%mod
                    for a in n:
                        ans *= a
                        ans %= mod
                    for a in p:
                        ans *= a
                        ans %= mod
                else:
                    ans = cand[0][0]*cand[0][1]%mod
                    for a in n:
                        ans *= a
                        ans %= mod
                    for a in p:
                        ans *= a
                        ans %= mod
print(ans)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
from functools import reduce, lru_cache
import sys, copy


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def inverse(self):
        return pow(self.x, MOD - 2, MOD)

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N, K = LI()
    A = LI()

    if K == N:
        print(reduce(lambda x, y: x * y, A, ModInt(1)))
        exit()

    plus = sorted([ai for ai in A if ai >= 0], reverse=True)
    minus = sorted([ai for ai in A if ai < 0])

    if len(plus) == 0:
        if K % 2 == 1:
            print(reduce(lambda x, y: x * y, minus[-K:], ModInt(1)))
        else:
            print(reduce(lambda x, y: x * y, minus[:K], ModInt(1)))
        exit()

    ip, im = 0, 0
    ans = ModInt(1)

    j = 0

    while True:
        if j == K:
            break
        if j == K - 1:
            ans *= plus[ip]
            break

        
        if len(plus) - ip >= 2 and len(minus) - im >= 2:
            p = plus[ip] * plus[ip+1]
            m = minus[im] * minus[im+1]
            if p > m:
                ans *= plus[ip]
                ip += 1
                j += 1
            else:
                ans *= m
                im += 2
                j += 2
        elif len(plus) - ip >= 2:
            ans *= plus[ip]
            ip += 1
            j += 1
        elif len(minus) - im >= 2:
            ans *= minus[im] * minus[im+1]
            im += 2
            j += 2

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(key=lambda x:-abs(x))

if N==K:
    ans = 1
    for i in range(N):
        ans *= A[i]
        ans %= mod
elif A[K-1]==0:
    ans = 0
else:
    p = []
    p_ = []
    n = []
    n_ = []
    for i in range(N):
        a = A[i]
        if i<K:
            if a>0:
                p.append(a)
            elif a<0:
                n.append(a)
        else:
            if a>0:
                p_.append(a)
            elif a<0:
                n_.append(a)
    if len(n)%2==0:
        ans = 1
        for a in n:
            ans *= a
            ans %= mod
        for a in p:
            ans *= a
            ans %= mod
    else:
        if len(p)+len(p_)==0:
            if len(n)+len(n_)==N:
                n += n_
                ans = 1
                for i in range(K):
                    ans *= n[-i-1]
                    ans %= mod
            else:
                ans = 0
        else:
            if len(p)==0:
                n.pop()
                ans = p_[0]
                for a in n:
                    ans *= a
                    ans %= mod
            else:
                cand = []
                ap = p.pop()
                if p_:
                    cand.append([ap,p_[0]])
                an = n.pop()
                if n_:
                    cand.append([an,n_[0]])
                if len(cand)==2:
                    ap1,ap2 = cand[0]
                    an1,an2 = cand[1]
                    ans = max(ap1*ap2,an1*an2)%mod
                    for a in n:
                        ans *= a
                        ans %= mod
                    for a in p:
                        ans *= a
                        ans %= mod
                else:
                    ans = cand[0][0]*cand[0][1]%mod
                    for a in n:
                        ans *= a
                        ans %= mod
                    for a in p:
                        ans *= a
                        ans %= mod
print(ans)

Solution (Python):
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return x2, y2, n

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None 
    else:
        return x % mod

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A, key=abs, reverse=True)
cand = []
minus = False
last_plus, last_minus = None, None
for a in A[:K]:
    cand.append(a)
    if a < 0: minus = not minus; last_minus = a
    elif a > 0: last_plus = a
    else: minus = False
ans = reduce(lambda x, y: x * y % MOD, cand)
if minus and K != N:
    non_neg, neg = None, None
    for a in A[K:]:
        if a >= 0 and non_neg is None: non_neg = a
        elif a < 0 and neg is None: neg = a
        if non_neg is not None and neg is not None: break
    if non_neg is None:
        if last_plus:
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans = reduce(lambda x, y: x * y % MOD, A[::-1][:K])
    elif neg is None:
        ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
    else:
        if last_plus and abs(last_plus * non_neg) < abs(last_minus * neg):
            ans *= modular_inverse(last_plus, MOD) * neg; ans %= MOD
        else:
            ans *= modular_inverse(last_minus, MOD) * non_neg; ans %= MOD
print(ans)

Solution (Python):

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


def solve():
    n, k = LI()
    a = LI()
    a.sort(key=abs, reverse=True)
    ans = 1
    if n - a.count(0) < k:
        print(0)
        return
    t = 0
    L = None
    R= inf
    for ai in a[:k]:
        if ai < 0:
            t ^= 1
            L = ai
        if ai > 0:
            R = ai
        ans *= ai
        ans %= mod
    if k == n:
        print(ans)
        return
    if t:
        if max(a) <= 0:
            ans = 1
            for i in range(k):
                ans *= a[-i - 1]
                ans %= mod
            print(ans)
        else:
            A = min(a[k:])
            B = max(a[k:])
            if A >= 0:
                ans *= pow(L, mod - 2, mod)
                ans *= B
            else:
                if A * L > B * R:
                    ans *= pow(R, mod - 2, mod)
                    ans *= A
                else:
                    ans *= pow(L, mod - 2, mod)
                    ans *= B
            print(ans % mod)
    else:
        print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys

if(__name__ == "__main__"):

    N, K = map( int, input().strip().split() )
    divisor = 10**9+7
    list_a = list( map( int, input().strip().split() ) )
    multiplies = 1
    if(N==K):
        for i in range(N):
            multiplies = multiplies * list_a[i] % divisor
    else:
        list_a.sort()
        """
        解が負になるのはN>Kの時には
        正の項が1つもなく、Kが奇数の時
        """
        if(list_a[-1] < 0 and K % 2 != 0):
            """
            全て負の項
            list_a = [-5, -3, -1]のようにソートされている
            末尾の項から選んでいく
            """
            for i in range(K):
                multiplies = multiplies * list_a[N-1-i] % divisor
        elif(K==1):
            multiplies = list_a[N-1]
        else:
            left = 0
            right = N-1
            if(K%2!=0):
                multiplies = multiplies * list_a[right] % divisor
                right -= 1
            multiply_left = list_a[left] * list_a[left+1]
            multiply_right = list_a[right] * list_a[right-1]

            for s in range(K//2-1):
                if(multiply_left < multiply_right):
                    multiply_right %= divisor
                    multiplies = multiplies * multiply_right % divisor
                    right -= 2
                    multiply_right = list_a[right] * list_a[right-1]

                else:
                    multiply_left%=divisor
                    multiplies = multiplies * multiply_left % divisor
                    left += 2
                    multiply_left = list_a[left] * list_a[left+1]

            if(multiply_left < multiply_right):
                multiply_right %= divisor
                multiplies = multiplies * multiply_right % divisor

            else:
                multiply_left%=divisor
                multiplies = multiplies * multiply_left % divisor


    print(multiplies)

Solution (Python):
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)

ans = 0

if n == k:
    ans = 1
    for i in range(n):
        ans *= a[i]
        ans %= mod
    print(ans)
    exit()

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
        tmp %= mod
    ans = -tmp

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x % mod)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x % mod)


for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    first = False
    if len(pl) >= k-p:
        first = True
        pl_ind = k-p
        mn_ind = p
        break

if not first:
    print(ans % mod)
    exit()

while pl_ind-2 > -1 and mn_ind+1 < len(mn):
    if pl[pl_ind-1]*pl[pl_ind-2] <= mn[mn_ind]*mn[mn_ind+1]:
        pl_ind -= 2
        mn_ind += 2
    else:
        break

if pl_ind < 0:
    ans = mn_cum[mn_ind]
else:
    ans = pl_cum[pl_ind]*mn_cum[mn_ind]

print(ans % mod)

Solution (Python):


import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    "void()"

    posi = [x for x in XS if x >= 0]
    nega = [x for x in XS if x < 0]

    nega.sort(reverse=True)
    posi.sort()

    if K == N:
        
        ret = 1
        for i in range(N):
            ret *= XS[i]
            ret %= MOD
        return ret

    if not posi and K % 2:
        
        
        ret = 1
        for i in range(K):
            ret *= nega[i]
            ret %= MOD
        return ret

    ret = 1
    while K:
        
        if K >= 2:
            if len(posi) >= 2:
                v = posi[-1] * posi[-2]
                if len(nega) >= 2:
                    w = nega[-1] * nega[-2]
                else:
                    w = -INF
                if v > w:
                    posi.pop()
                    posi.pop()
                    ret *= v
                    ret %= MOD
                else:
                    nega.pop()
                    nega.pop()
                    ret *= w
                    ret %= MOD

            else:
                w = nega[-1] * nega[-2]
                nega.pop()
                nega.pop()
                ret *= w
                ret %= MOD

            K -= 2
        else:
            ret *= posi[-1]
            ret %= MOD
            K -= 1
    return ret


def main():
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))
    print(solve(N, K, XS))


T1 = """
4 2
1 2 -3 -4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    12
    """


T2 = """
4 3
-1 -2 -3 -4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1000000001
    """


T3 = """
2 1
-1 1000000000
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1000000000
    """


T4 = """
10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    999983200
    """


def _test():
    import doctest
    doctest.testmod()


T5 = """
3 2
1 1 -1
"""


def test_T5():
    """
    >>> as_input(T5)
    >>> main()
    1
    """


T6 = """
3 2
1 -1 -1
"""


def test_T6():
    """
    >>> as_input(T6)
    >>> main()
    1
    """


T7 = """
3 2
2 -1 -1
"""


def test_T7():
    """
    >>> as_input(T7)
    >>> main()
    1
    """


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x >= 0:
        return 0
    elif x < 0:
        return 1


pl = []
mn = []

for x in a:
    if x >= 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0]
for i in range(k):
    c[b[i][1]] += 1


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    if c[1] % 2:
        ans = (-ans) % mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
    exit()

if len(mn) == n and k % 2:
    tmp = 1
    for i in range(k):
        tmp *= mn[-i-1]
        tmp %= mod
    ans = -tmp
    print(ans % mod)
    exit()

ans = 0

chk1 = False
chk2 = False

if c[0] <= len(pl) - 1:
    chk1 = True

if 0 < c[0] and c[1] <= len(mn)-1:
    chk2 = True

if chk1 and chk2:
    tmp1 = pl[c[0]]*pl[c[0]-1]
    tmp2 = mn[c[1]]*mn[c[1]-1]
    if tmp1 > tmp2:
        c[0] += 1
        c[1] -= 1
        print(solve(c))
    else:
        c[0] -= 1
        c[1] += 1
        print(solve(c))
elif chk1:
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif chk2:
    c[0] -= 1
    c[1] += 1
    print(solve(c))
else:
    print(solve(c))

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

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mi < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*pv) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)

Solution (Python):
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
    n -= 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)

Solution (Python):
n , k = map(int, input().split())
a = list(map(int, input().split()))
neg = []
pos = []
mod = 10**9+7
for i in range(n):
    if a[i] >= 0:
        pos.append(a[i])
    else:
        neg.append(a[i])
neg.sort()
pos.sort(reverse = True)
if (len(pos) == 0 and k % 2 == 1) or n == k:
    ans = 1
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        ans %= mod
    print(ans % mod)
else:
    
    from collections import deque
    ans = 1
    neg_new = []
    for i in range(0, len(neg)//2):
        neg_new.append(neg[2*i] * neg[2*i+1])
    neg_new = deque(sorted(neg_new, reverse = True))
    pos = deque(pos)
    if k % 2 == 1:
        k -= 1
        ans = pos.popleft()
    else:
        ans = 1
    while k > 0:
        if len(pos) >= 2 and len(neg_new) >= 1:
            if pos[0] * pos[1] > neg_new[0]:
                ans *= pos.popleft() * pos.popleft()
            else:
                ans *= neg_new.popleft()
        elif len(pos) >= 2:
            ans *= pos.popleft() * pos.popleft()
        else:
            ans *= neg_new.popleft()
        k -= 2
        ans %= mod
    print(ans % mod)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
a.sort()
mi = []
pl = []
if n == k:
    ans = 1
    for i in a:
        ans *= i
        ans %= mod
    print(ans)
    exit()
for i in a:
    if i < 0:
        mi.append(i)
    else:
        pl.append(i)
if pl == []:
    ans = 1
    count = 0
    if k%2:
        while count < k:
            ans *= a[-1-count]
            ans %= mod
            count += 1
    else:
        while count < k:
            ans *= a[count]
            ans %= mod
            count += 1
    print(ans)    
    exit()
pl = sorted(pl,reverse=True)
ip = 0
im = 0
if k%2:
    count = pl[0]
    k -= 1
    ip += 1
else:
    count = 1
while k > 0:
    check1 = True
    check2 = True
    if ip+2 <= len(pl):
        x = pl[ip]*pl[ip+1]    
    else:
        x = 1
        check1 = False
    if im+2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        y = 1
        check2 = False
    if x > y or (check1 and not check2):
        ip += 2
        count = (x*count)%mod
    else:
        if check2:
            im += 2
            count = (y*count)%mod
    if check1 == False and check2 == False:
        break
    k -= 2

print(count%mod)

Solution (Python):
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:
        n.append(A[i])
    else:
        p.append(A[i])
p.sort(reverse=True)
n.sort()
numplus=len(p)
if numplus==0:
    ans=1
    if K%2==1:
        for i in range(1,K+1):
            ans=(ans*n[i*(-1)])%MOD
    else:
        for i in range(K):
            ans=(ans*n[i])%MOD
elif N==K:
    ans=1
    for i in range(N):
        ans=(ans*A[i])%MOD
else:
    if numplus>=K:
        x=K
        if 0 in p:
            zero=p.index(0)
            len(p)-zero-1
    else:
        if (K-numplus)%2==1:
            x=numplus-1
        else:
            x=numplus
    ans=1
    for i in range(x):
        ans=(ans*p[i])%MOD
    for i in range(K-x):
        ans=(ans*n[i])%MOD
    temp=ans
    while x>1:
        if len(n)<(K-x+2):
            break
        if n[K-x]*n[K-x+1]<p[x-1]*p[x-2]:
            break
        temp=(temp*n[K-x]*n[K-x+1])%MOD
        temp=(temp*pow(p[x-1]*p[x-2],MOD-2,MOD))%MOD
        ans=temp
        x-=2
print(ans)

Solution (Python):
MOD=10**9+7
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))

num_neg=0
num_pos=0
num_zero=0
aalist=[]
for a in alist:
  if a>0:
    num_pos+=1
  elif a<0:
    num_neg+=1
  else:
    num_zero+=1
  aalist.append((abs(a),a))
aalist.sort(reverse=True)
    
if N==K:
  answer=1
  for a in alist:
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
  
pos_possible=True
if num_neg==N and K%2==1:
  pos_possible=False
    
if not pos_possible:
  aalist.sort()
  answer=1
  for i in range(K):
    aa,a=aalist[i]
    answer*=a
    answer%=MOD
  print(answer)
  sys.exit(0)
    
aalist.sort(reverse=True)

answer=1
sgn=1
pos_absmin=0
neg_absmin=0
for i in range(K):
  aa,a=aalist[i]
  answer*=a
  answer%=MOD
  if a>0:
    pos_absmin=a  
  elif a<0:
    neg_absmin=a
    sgn*=-1
  else:
    sgn=0

if sgn==0:
  print(0)    
elif sgn>0:
  print(answer)
else:
  pos_absmax=0
  neg_absmax=0
  for i in reversed(range(K,N)):
    aa,a=aalist[i]
    if a>0:
      pos_absmax=a
    else:
      neg_absmax=a
      
  
  if pos_absmin==0:
    answer*=pos_absmax
    answer*=pow(neg_absmin%MOD,MOD-2,MOD)
    answer%=MOD
  elif neg_absmin==0:
    answer*=neg_absmax%MOD
    answer*=pow(pos_absmin,MOD-2,MOD)
    answer%=MOD
  elif pos_absmin*pos_absmax<neg_absmin*neg_absmax:
    answer*=neg_absmax%MOD
    answer*=pow(pos_absmin,MOD-2,MOD)
    answer%=MOD
  else:
    answer*=pos_absmax
    answer*=pow(neg_absmin%MOD,MOD-2,MOD)
    answer%=MOD
  
  print(answer)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True, key = lambda x: abs(x))
mod = 10**9+7
nega = 0
posi = 0
zero = 0
for i in range(n):
    if a[i] > 0:
        posi += 1
    elif a[i] == 0:
        zero += 1
    else:
        nega += 1

if n == k:
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod
    if nega%2 == 1:
        ans *= -1

elif posi == 0:

    if k % 2 == 0:
        ans = 1
        for i in range(k):
            ans *= abs(a[i])
            ans %= mod

    else:
        if zero > 0:
            ans = 0
        else:
            a.reverse()
            ans = 1
            for i in range(k):
                ans *= abs(a[i])
                ans %= mod

            ans *= -1


else:
    posi = 0
    nega = 0
    zero = 0
    ans = 1
    for i in range(k):
        ans *= abs(a[i])
        ans %= mod

    for i in range(k):
        if a[i] > 0:
            posi += 1
        elif a[i] < 0:
            nega += 1
        else:
            zero += 1

    if zero > 0:
        ans = 0

    elif nega % 2 != 0:
        minposi = 0
        minnega = 0
        for i in range(k-1, -1, -1):
            if a[i] > 0:
                if minposi == 0:
                    minposi = a[i]
            else:
                if minnega == 0:
                    minnega = a[i]

        maxposi = 0
        maxnega = 0
        for i in range(k, n):
            if a[i] > 0:
                if maxposi == 0:
                    maxposi = a[i]
            elif a[i] < 0:
                if maxnega == 0:
                    maxnega = a[i]


        if minposi == 0:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)

        elif abs(minposi*maxposi) <= abs(minnega*maxnega):
            ans *= pow(abs(minposi), mod-2, mod)
            ans *= abs(maxnega)

        else:
            ans *= pow(abs(minnega), mod-2, mod)
            ans *= abs(maxposi)



print(ans % mod)

Solution (Python):
import sys


def solve(n, k, aaa):
    MOD = 10 ** 9 + 7

    if n == k:
        ans = 1
        for a in aaa:
            ans = ans * a % MOD
        return ans

    pos = []  
    neg = []
    for a in aaa:
        if a >= 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)

    if len(pos) == 0:
        if k % 2 == 1:
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)
    ans = 1
    r = k

    if r % 2 == 1:
        ans = ans * pos.pop() % MOD
        r -= 1

    while r > 0:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pos.pop() * pos.pop() % MOD
            else:
                ans = ans * neg.pop() * neg.pop() % MOD
        r -= 2

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))