#!/usr/bin/env python3
import sys
import heapq

MOD = 1000000007  # type: int

def containPositive(arr):
    for a in arr:
        if a >= 0:
            return True
    return False

def solve(N: int, K: int, A: "List[int]"):
    if N == K:
        m = 1
        for a in A:
            m = m*a%MOD
        print(m)
    elif not containPositive(A):
        A = list(reversed(sorted(A))) if K%2 == 1 else list(sorted(A))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else:
        m = 1
        B = [(abs(a),a) for a in A]
        B = list(reversed(sorted(B)))
        lastNegative = 0
        lastPositive = 1
        hadPositive = False
        for i in range(K):
            a = B[i][1]
            if a < 0:
                if lastNegative == 0:
                    lastNegative = a
                else:
                    m = m*lastNegative*a%MOD
                    lastNegative = 0
            else:
                if a > 0 and lastPositive != 1:
                    m = m*lastPositive%MOD
                if a > 0:
                    lastPositive = a
                    hadPositive = True
                else:
                    m=m*a%MOD
        if lastNegative == 0:
            print(m*lastPositive%MOD)
        else:
            nextNegative = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            if nextNegative == 0:
                m = m*B[K][1]
                print(m*lastPositive%MOD)
            else:
                c1 = lastNegative*nextNegative
                nextPositive = 0
                k = K
                while k < N:
                    a = B[k][1]
                    if a >=0:
                        nextPositive = a
                        break
                    k+=1
                c2 = nextPositive*lastPositive
                if not hadPositive:
                    m = m*nextPositive%MOD
                    # print("here")
                    # print(B[K-1],B[K],B[K+1],B[K+2])
                    # print(hadPositive)
                    # print(lastNegative,nextNegative)
                    # print(lastPositive,nextPositive)
                    print(m)
                    exit()
                if c1 > c2 or not hadPositive:
                    m = m*lastNegative*nextNegative%MOD
                    # print("here")
                    # print(B[K-1],B[K],B[K+1],B[K+2])
                    # print(hadPositive)
                    # print(lastNegative,nextNegative)
                    # print(lastPositive,nextPositive)
                    print(m)
                else:
                    # print("here")
                    # print("here")
                    # print(hadPositive)
                    # print(lastNegative,nextNegative)
                    # print(lastPositive,nextPositive)
                    m =m*nextPositive*lastPositive%MOD
                    print(m)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 103876