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
from bisect import bisect_left

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

pos = A[bisect_left(A, 0):]
pos.reverse()
neg = A[:bisect_left(A, 0)]

mod = 10**9+7
ans = 1
if len(pos) == 0 and K % 2 == 1:
    for i in range(K):
        ans *= neg[-i-1]
        ans %= mod
elif N == K:
    for i in range(K):
        ans *= A[i]
        ans %= mod
else:
    p, n = 0, 0
    for i in range(0, K-1, 2):
        v1 = 0
        v2 = 0
        if K % 2 == 0:
            if len(pos) >= p + 2:
                v1 = pos[p] * pos[p+1]
        else:
            if len(pos) >= p + 3:
                v1 = pos[p] * pos[p+1]

        if len(neg) >= n + 2:
            v2 = neg[n] * neg[n+1]

        if v2 > v1:
            ans *= v2
            ans %= mod
            n += 2
        else:
            ans *= v1
            ans %= mod
            p += 2

    if K % 2 == 1:
        ans *= pos[p]
        ans %= mod

print(ans)