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
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))

mod = 10**9+7
ans = 1
mi = []
pl = []
for a in A:
    if a < 0:
        mi.append(a)
    else:
        pl.append(a)

if N == K:
    for a in A:
        ans *= a
        ans %= mod
    print(ans)
    exit()
if pl == []:
    if K%2:
        for k in range(K):
            ans *= mi[-1-k]
            ans %= mod
    else:
        for k in range(K):
            ans *= mi[k]
            ans %= mod
    print(ans)
    exit()

pl = pl[::-1]

ip = 0
im = 0
if K % 2:
    ans = pl[0]
    ip += 1
    K -= 1

while K > 0:
    check = True
    if ip + 2 <= len(pl):
        x = pl[ip]*pl[ip+1]
    else:
        x = 1
    if im + 2 <= len(mi):
        y = mi[im]*mi[im+1]
    else:
        check = False
        y = 1

    if x >= y or check == False:
        ans *= x
        ans %= mod
        ip += 2
    else:
        ans *= y
        ans %= mod
        im += 2
    K -= 2
print(ans)
    
