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).
N, K = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10**9 + 7

A_abs = [abs(a) for a in A]
A_is_negative = [a < 0 for a in A]


A_abs, A_is_negative, A = zip(*sorted(zip(A_abs, A_is_negative, A), key=lambda x: x[0], reverse=True))

ans = 1
ans_is_negative = 0

for i in range(K-1):
    ans *= A[i]
    if A_is_negative[i]:
        
        ans_is_negative = 1 - ans_is_negative
        last_negative = i


if ans_is_negative and A_is_negative[K-1]:
    ans *= A[K-1]
    ans %= MOD
    print(ans)
elif ans_is_negative and not A_is_negative[K-1]:
    
    for i in range(K, N):
        if A_is_negative[i]:
            ans *= A[K-1]
            ans %= MOD
            print(ans)
            exit()
    
    
    tar = A[last_negative]
    tar_inv = pow(tar, MOD-2, MOD)
    ans *= tar_inv
    ans %= MOD
    ans *= A[K-1]
    ans %= MOD
    ans *= A[K]
    ans %= MOD
    print(ans)
elif not ans_is_negative and A_is_negative[K-1]:
    
    for i in range(K, N):
        if not A_is_negative[i]:
            ans *= A[K-1]
            ans %= MOD
            print(ans)
            exit()
    .
    
    ans = 1
    for i in range(1, K+1):
        ans *= A[-i]
        ans %= MOD
    print(ans)
else:
    
    ans *= A[K-1]
    ans %= MOD
    print(ans)

from heapq import heappush, heappop


N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

MOD = 10**9 + 7


if N == K:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)

elif max(A) < 0 and K % 2 == 1:
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
    print(ans)
else:
    

    
    

    if K%2 == 1:
        ans = A.pop(0)  
        n = (K-1)//2
    else:
        ans = 1
        n = K//2

    
    A = sorted(A, key=lambda x: abs(x), reverse=True)

    
    cand = []  

    BIGINT = 10**9 + 1  
    tmp1 = BIGINT
    tmp2 = BIGINT

    for a in A:
        if a >= 0:
            if tmp1 == BIGINT:
                tmp1 = a
            else:
                heappush(cand, -tmp1*a)
                tmp1 = BIGINT
        else:
            if tmp2 == BIGINT:
                tmp2 = a
            else:
                heappush(cand, -tmp2*a)
                tmp2 = BIGINT

    
    for i in range(n):
        ans *= -heappop(cand)
        ans %= MOD
    print(ans)
