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

if N == K:
    #全部かけて出力
    ans = 1
    for i in range(0,N,1):
        ans = (ans*A[i])%MOD
    print(ans)
    exit()

plus = []
minus = []
for i in range(0,N,1):
    if A[i] < 0:
        minus.append(-A[i])
    if A[i] > 0:
        plus.append(A[i])
    if A[i]==0:
        minus.append(0)
        plus.append(0)


if len(plus)==0 and K%2 == 1:
    minus.sort()
    ans = 1
    for i in range(0,K,1):
        ans = (ans*(-minus[i]))%MOD
    print(ans)
    exit()
        


#既に絶対値を格納
plus.sort(reverse=True)
minus.sort(reverse=True)

ans = 1
if K%2 ==1:#奇数
    ans = ans*plus[0]#一番でかいやつ
    plus.pop(0)

pairs = []
for i in range(1,len(plus),2):
    pairs.append(plus[i]*plus[i-1])
for i in range(1,len(minus),2):
    pairs.append(minus[i]*minus[i-1])
pairs.sort(reverse=True)
#でかいほうから K//2 こかける

for i in range(0,K//2,1):
    ans = (ans * pairs[i])%MOD

print(ans)


