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).



Sample input:
4 2
1 2 -3 -4


Sample output:
12

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

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 len(list(filter(lambda x: x>=0,A))) == 0 and K%2 == 1: # Can't be made positive, use from lower absolute value
        A = list(reversed(sorted(A)))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else: # We can make some combination to make positive result in this condition
        m = 1
        B = list(reversed(sorted([(abs(a),a) for a in A]))) # Make a sorted array with absolute value
        lastNegative = 0
        lastPositive = 1
        hadPositive = False
        for i in range(K): # Fill K elements with keeping the result positive. 
            a = B[i][1]
            if a < 0: 
                if lastNegative == 0: # If got a negative value and there are no last negative value kept aside
                    lastNegative = a # Keep this value aside and won't multiply to the result.
                else: # If got a negative value and there are negative value aside last time the loop found negative value, just multiply these 2 values to mul and reset the kept value.
                    m = m*lastNegative*a%MOD 
                    lastNegative = 0
            else:
                if a > 0: # If we got positive value, the value need to be kept aside for once to be swapped another negative value.
                    if hadPositive: # If there is positive value kept aside before, multiply that value to the result
                        m = m*lastPositive%MOD
                    lastPositive = a # The newest value need to be kept aside
                    hadPositive = True
                else:
                    m=m*a%MOD # Only for zero
        if lastNegative == 0: # This assumes the result is already positive. No need to tweak. But need to multiply the last positive value
            print(m*lastPositive%MOD)
        else:
            # Find next negative/positive value after Kth elements
            nextNegative = 0
            nextPositive = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            for i in range(K,N):
                a = B[i][1]
                if a >=0:
                    nextPositive = a
                    break
            if not hadPositive: # This array must contain some non-negative value. This means the result value could be positive. But if there were no positive values in the first K values sorted by the absolute value, use just next positive value instead of the last negative values.
                print(m*nextPositive%MOD)
            elif lastNegative*nextNegative > nextPositive*lastPositive:
                print(m*lastNegative*nextNegative%MOD)
            else:
                print(m*nextPositive*lastPositive%MOD)


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

mod = 10**9 + 7

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

se = []
hu = []

for e in a:
    if e > 0:
        se.append(e)
    elif e < 0:
        hu.append(-e)
se.sort()
hu.sort()

S = len(se)
H = len(hu)

Z = n - S - H

if Z + k > n:
    print(0)
    exit()

#negative個数の最小と最大
Hmi = max(0,k-Z-S)
Hma = min(k,H)

#正が無理なパターン
if Hmi == Hma and Hmi%2 == 1:
    if Z > 0:
        print(0)
    else:
        hu_mul = 1
        for i in range(Hmi):
            hu_mul = hu_mul*hu[i]%mod
        se_mul = 1
        for i in range(k-Hmi):
            se_mul = se_mul*se[i]%mod
        print((-hu_mul)*se_mul%mod)
else:
    se = se[::-1]
    hu = hu[::-1]
    hu_mul = 1
    se_mul = 1
    for i in range(Hmi):
        hu_mul = hu_mul*hu[i]%mod
    
    if Hmi%2 == 0:
        k -= Hmi
    else:
        hu_mul = hu_mul*hu[Hmi]%mod
        Hmi += 1
        k -= Hmi
    hidx = Hmi
    sidx = 0
    

    if k%2 == 1:
        if S == 0:
            print(0)
            exit()
        se_mul = se[0]
        sidx += 1
        k -= 1


    while k > 0:
        if hidx + 1 >= H and sidx + 1 >= S:
            print(0)
            exit()
        elif hidx + 1 >= H:
            se_mul = se_mul*(se[sidx]*se[sidx+1]%mod)%mod
            sidx += 2
        elif sidx + 1 >= S:
            hu_mul = hu_mul*(hu[hidx]*hu[hidx+1]%mod)%mod
            hidx += 2
        else:
            if hu[hidx]*hu[hidx+1] > se[sidx]*se[sidx+1]:
                hu_mul = hu_mul*(hu[hidx]*hu[hidx+1]%mod)%mod
                hidx += 2
            else:
                se_mul = se_mul*(se[sidx]*se[sidx+1]%mod)%mod
                sidx += 2
        k -= 2

    print((hu_mul)*se_mul%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

if all(a < 0 for a in A) and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for a in A[:K]:
        ans = ans * a % MOD
    print(ans)
    exit(0)

p = []
n = []
for a in A:
    if a < 0:
        heappush(n, a)
    else:
        heappush(p, -a)

ans = 1
cnt = 0
while cnt < K:
    if cnt == K - 1:
        if len(p) > 0:
            ans = ans * -heappop(p) % MOD
        else:
            ans = ans * max(n) % MOD
        cnt += 1
        break
    if len(p) < 1:
        ans = ans * heappop(n) * heappop(n) % MOD
        cnt += 2
    elif len(n) < 2:
        ans = ans * -heappop(p) % MOD
        cnt += 1
    else:
        p0, p1 = -p[0], -p[1] if len(p) > 1 else 1
        if p0 * p1 > n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        else:
            ans = ans * heappop(n) * heappop(n) % MOD
            cnt += 2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = int(1e9+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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

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 len(list(filter(lambda x: x>=0,A))) == 0 and K%2 == 1:
        A = list(reversed(sorted(A)))
        m = 1
        for i in range(K):
            m = m*A[i]%MOD
        print(m)
    else: # We can make some combination to make positive result in this condition
        m = 1
        B = list(reversed(sorted([(abs(a),a) for a in A]))) # Make a sorted array with absolute value
        lastNegative = 0
        lastPositive = 1
        hadPositive = False
        for i in range(K): # Fill K elements with keeping the result positive. 
            a = B[i][1]
            if a < 0: 
                if lastNegative == 0: # If got a negative value and there are no last negative value kept aside
                    lastNegative = a # Keep this value aside and won't multiply to the result.
                else: # If got a negative value and there are negative value aside last time the loop found negative value, just multiply these 2 values to mul and reset the kept value.
                    m = m*lastNegative*a%MOD 
                    lastNegative = 0
            else:
                if a > 0: # If we got positive value, the value need to be kept aside for once to be swapped another negative value.
                    if hadPositive: # If there is positive value kept aside before, multiply that value to the result
                        m = m*lastPositive%MOD
                    lastPositive = a # The newest value need to be kept aside
                    hadPositive = True
                else:
                    m=m*a%MOD # Only for zero
        if lastNegative == 0: # This assumes the result is already positive. No need to tweak. But need to multiply the last positive value
            print(m*lastPositive%MOD)
        else:
            # Find next negative value after Kth elements
            nextNegative = 0
            for i in range(K,N):
                b = B[i][1]
                if b < 0:
                    nextNegative = b
                    break
            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: # This array contain some non-negative value. This means the result value could be positive. But if there were no positive values in the first K values sorted by the absolute value, use just next positive value instead of the last negative values.
                m = m*nextPositive%MOD
                print(m)
                exit()
            if c1 > c2:
                m = m*lastNegative*nextNegative%MOD
                print(m)
            else:
                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()

Submission status: Accepted

Solution code:
#!/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) and K%2 == 1:
        A = list(reversed(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: # This array contain some non-negative value. This means the result value could be positive. But if there were no positive values in the first K values sorted by the absolute value, use just next positive value instead of the last negative values.
                    m = m*nextPositive%MOD
                    print(m)
                    exit()
                if c1 > c2:
                    m = m*lastNegative*nextNegative%MOD
                    print(m)
                else:
                    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()

Submission status: Accepted

Solution code:
M=10**9+7
n,k,*a=map(int,open(y:=0).read().split())
a.sort()
x=s=1
r=k
while r>1:
 if(t:=a[y]*a[y+1])>a[-x]*a[~x]:s=s*t%M;y+=2;r-=2
 else:s=s*a[-x]%M;x+=1;r-=1
if r:s*=a[-x]
if a[-1]<0<k%2:
 s=1
 for i in a[-k:]:s=s*i%M
print(s%M)

Submission status: Accepted

Solution code:
#!/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: # This array contain some non-negative value. This means the result value could be positive. But if there were no positive values in the first K values sorted by the absolute value, use just next positive value instead of the last negative values.
                    m = m*nextPositive%MOD
                    print(m)
                    exit()
                if c1 > c2:
                    m = m*lastNegative*nextNegative%MOD
                    print(m)
                else:
                    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()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, K = inm()
A = inl()
B = [(abs(a), a < 0) for a in A]
B.sort(reverse=True)

MOD = 10 ** 9 + 7


def solve():
    fs = []
    negmin = posrep = None
    posmin = negrep = None
    negcnt = 0
    for i in range(N):
        v, neg = B[i]
        if len(fs) < K:
            fs.append(v)
            if neg:
                negcnt += 1
                negmin = v
            else:
                posmin = v
        elif neg and negrep is None:
            negrep = v
        elif not neg and posrep is None:
            posrep = v
    if negcnt % 2 == 0:
        a0 = 1
        for x in fs:
            a0 = (a0 * x) % MOD
        return a0

    a1 = a2 = None
    if negmin is not None and posrep is not None:
        a1 = 1
        replaced = False
        for x in fs:
            if x == negmin and not replaced:
                a1 = (a1 * posrep) % MOD
                replaced = True
            else:
                a1 = (a1 * x) % MOD
    if posmin is not None and negrep is not None:
        a2 = 1
        replaced = False
        for x in fs:
            if x == posmin and not replaced:
                a2 = (a2 * negrep) % MOD
                replaced = True
            else:
                a2 = (a2 * x) % MOD

    if a1 is None and a2 is None:
        a3 = 1
        sign = 1
        for x, neg in B[N - K :]:
            a3 = (a3 * x) % MOD
            if neg:
                sign *= -1
        return (MOD + sign * a3) % MOD

    if a1 is None:
        return a2
    if a2 is None:
        return a1

    if posrep * posmin < negrep * negmin:
        return a2
    else:
        return a1


print(solve())

Submission status: Accepted

Solution code:
#!/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()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    mod = 10**9 + 7
    p = 1
    if n == k:
        for ai in a:
            p = p * ai % mod
        print(p)
        return
    if a[0] < 0 and k % 2:
        for ai in a[:k]:
            p = p * ai % mod
        print(p)
        return
    b = sorted([(abs(ai), ai) for ai in a], reverse=True)
    s = 0
    for ba, bb in b[:k]:
        p = p * ba % mod
        if bb < 0:
            s += 1
    if s % 2 == 0:
        print(p)
        return
    pa, na, pb, nb = [-1] * 4
    for ba, bb in b[:k]:
        if bb < 0:
            na = ba
        else:
            pa = ba
    for ba, bb in b[k:][::-1]:
        if bb < 0:
            nb = ba
        else:
            pb = ba
    if pa == -1 or nb == -1:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    elif pb == -1 or na == -1:
        print(p * nb * pow(pa, mod - 2, mod) % mod)
    elif pa * pb > na * nb:
        print(p * pb * pow(na, mod - 2, mod) % mod)
    else:
        print(p * nb * pow(pa, mod - 2, mod) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    plus = []
    minus = []
    for a in A:
        if a >= 0:
            heapq.heappush(plus, -a)
        else:
            heapq.heappush(minus, a)

    ans = 1

    # 絶対マイナスになる場合
    if len(plus) < K - min((K - K % 2), (len(minus) - len(minus) % 2)):
        plus = []
        minus = []
        for a in A:
            if a >= 0:
                heapq.heappush(plus, a)
            else:
                heapq.heappush(minus, -a)

        while K > 0:
            if plus:
                x = plus[0]
            else:
                x = float("inf")

            if minus:
                y = -minus[0]
            else:
                y = float("inf")

            if abs(x) <= abs(y):
                ans *= x
                if plus:
                    heapq.heappop(plus)
            else:
                ans *= y
                if minus:
                    heapq.heappop(minus)

            ans %= MOD
            K -= 1

        print(ans)

    else:
        while K > 0:
            if K >= 2 and len(minus) >= 2 and len(plus) >= 2:
                x1 = plus[0]
                x2 = plus[1]
                y1 = minus[0]
                y2 = minus[1]
                if x1 * x2 <= y1 * y2:
                    y1 = heapq.heappop(minus)
                    y2 = heapq.heappop(minus)
                    ans *= (y1 * y2)
                    ans %= MOD
                    K -= 2
                else:
                    x1 = -heapq.heappop(plus)
                    ans *= x1
                    ans %= MOD
                    K -= 1
            elif K >= 2 and len(minus) >= 2:
                y1 = heapq.heappop(minus)
                y2 = heapq.heappop(minus)
                ans *= (y1 * y2)
                ans %= MOD
                K -= 2
            else:
                x = -heapq.heappop(plus)
                ans *= x
                ans %= MOD
                K -= 1

        print(ans % MOD)


if __name__ == '__main__':
    main()