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

Examples

Input

4 2
1 2 -3 -4


Output

12


Input

4 3
-1 -2 -3 -4


Output

1000000001


Input

2 1
-1 1000000000


Output

1000000000


Input

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1


Output

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