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
M=10**9+7
n,k,*l=map(int,open(0).read().split())
lp,lm=[],[]
for i in l:
  if i<0: lm+=[i]
  else: lp+=[i]
cp,cm=len(lp),len(lm)
ok=0
if cp:
  if n==k: ok=1-cm%2
  else: ok=1
else: ok=1-k%2
a=1
if ok<1:
  l.sort(key=lambda x:abs(x))
  for i in range(k): a=a*l[i]%M
else:
  lp.sort()
  lm.sort(reverse=1)
  if k%2: a=lp.pop()
  p=[]
  while len(lp)>1: p+=[lp.pop()*lp.pop()]
  while len(lm)>1: p+=[lm.pop()*lm.pop()]
  p.sort(reverse=1)
  for i in range(k//2): a=a*p[i]%M
print(a)