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

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
MOD = 10**9+7

n0, n1 = bisect.bisect_left(A, 0), bisect.bisect_left(A, 1)
if N - (n1 - n0) < K:
    print(0)
    exit()

m, z, p= n0, n1 - n0, N - n1
if K - p == min(K, m) and (K - p) % 2 == 1:
    ans = 1
    for a in sorted([abs(x) for x in A])[:K]:
        ans = (ans * a) % MOD
    print((-ans) % MOD)
else:
    if K % 2 != 0:
        ans, i, j = A[-1], N-2, 0
    else:
        ans, i, j = 1, N-1, 0
    
    for _ in range(K//2):
        if i <= n1:
            pos = False
        elif j >= n0-1:
            pos = True
        elif A[i] * A[i-1] > A[j] * A[j+1]:
            pos = True
        else:
            pos = False

        if pos:
            ans = (ans * ((A[i] * A[i-1]) % MOD)) %MOD
            i -= 2
        else:
            ans = (ans * ((A[j] * A[j+1]) % MOD)) %MOD
            j += 2
    print(ans)