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
def prod(A):
    r = 1
    for a in A:
        r *= abs(a)
        r %= mod
    return r

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), key=abs, reverse=True)

Ak = A[:K]
m = len([a for a in Ak if a<0])

if m%2==0:
    print(prod(Ak))
    exit()

r_p = [a for a in A[K:] if a>=0]
r_n = [a for a in A[K:] if a<=0]
a_p = [a for a in Ak    if a> 0]
a_n_min = max([a for a in Ak if a< 0])

ans1 = ans2 = None
if r_p:
    v1 = abs(a_n_min)
    w1 = max(r_p)
    ans1 = prod(Ak)*pow(v1, mod-2, mod) * w1 % mod
    
if a_p and r_n:
    v2 = min(a_p)
    w2 = abs(min(r_n))
    ans2 = prod(Ak)*pow(v2, mod-2, mod) * w2 % mod
    
if ans1 and ans2:
    print(ans1 if w1*v2>=w2*v1 else ans2)
    exit()

if ans1:
    print(ans1)
    exit()

if ans2:
    print(ans2)
    exit()

print((-prod(A[::-1][:K]))%mod)
