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

A.sort()

mod = int(1e9+7)
AM = []
AP = []
AZC = 0
for a in A:
  if a < 0:
    AM.append(a)
  elif a == 0:
    AZC += 1
  else:
    AP.append(a)

#print(AM)
#print(AP)
#print(AZC)
# zero選ばないとだめならゼロ
if N-K < AZC:
  print(0)
  exit(0)

if N == K:
  wk = 1
  for a in A:
    wk *= a
    wk %= mod
  print(wk)
  exit(0)
  
# minusしか選べないケースってあるの？
# AMしかなくて、Kがodd
# zeroが一つでもあればZERO
if len(AP) == 0 and K%2 == 1:
  if AZC > 0:
    print(0)
  else:
    wk = 1
    for i in range(K):
      wk *= AM[-1-i]
      wk %= mod
    print(wk)
  exit(0)  
   
# plusを狙える
# K odd -> plus max 1
# K even -> ２個いちで選んで行ってMAXを
wk = 1
if K%2 == 1:
  wk *= AP.pop(-1)
  wk %= mod
  
K = K // 2
mi, pi = 0, 0
AP = AP[::-1]
while K>0:
  mwk = AM[mi] * AM[mi + 1] if mi + 1 < len(AM) else 0
  pwk = AP[pi] * AP[pi + 1] if pi + 1 < len(AP) else 0
  if mwk <= pwk:
    wk *= pwk % mod
    pi += 2
  else:
    wk *= mwk % mod
    mi += 2
  #print(wk)
  wk %= mod
  K -= 1
print(wk)
