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 = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
s, t = [], []  # 正、負の配列
for i in a:
  if i < 0:
    t.append(i)
  else:
    s.append(i)
S, T = len(s), len(t)
is_positive = False  # 積が正である
if S > 0:
  # 正の数が0より大きい
  if n == k:
    # nとkが同じ
    is_positive = (T % 2 == 0) # 負の数が偶数個のとき、積は正
  else:
    is_positive = True
else:
  is_positive = (k % 2 == 0)

ans = 1
if not is_positive:
  a.sort(key=abs)
  for i in range(k):
    ans = ans * a[i] % MOD
else:
  s.sort()
  t.sort(reverse=True)
  if k % 2 == 1:
    ans = ans * s.pop(-1) % MOD
  p = []
  while(len(s) >= 2):
    x = s.pop(-1)
    x *= s.pop(-1)
    p.append(x)
  while(len(t) >= 2):
    x = t.pop(-1)
    x *= t.pop(-1)
    p.append(x)
  p.sort(reverse=True)
  for i in range(k // 2):
    ans = ans * p[i] % MOD
print(ans)