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()))
pos = []
neg = []
for v in A:
	if v >= 0: pos.append(v)
	else: neg.append(-v)

pos.sort(reverse=True)
neg.sort(reverse=True)

MOD = 10 ** 9 + 7
ppos = [1] * (len(pos)+1)
pneg = [1] * (len(neg)+1)

for i, v in enumerate(pos):
	ppos[i+1] = ppos[i] * v % MOD
for i, v in enumerate(neg):
	pneg[i+1] = pneg[i] * v % MOD

i = j = 0

while i + j < K:
	if i == len(pos): j += 1
	elif j == len(neg) or pos[i] >= neg[j]: i += 1
	else: j += 1

if j % 2 == 1:
	v = (-1, -1, -1)
	if i and j < len(neg):
		v = (neg[j-1] * neg[j], i-1, j+1)

	if i < len(pos) and j:
		v = max(v, (pos[i-1] * pos[i], i+1, j-1))

	if v[0] == -1:
		X = pos + neg
		X.sort()
		r = 1
		for v in X[:K]: r = r * v % MOD
		print(-r % MOD)
		raise SystemExit

	i, j = v[1:]

r = 1
for x in pos[:i]: r = r * x % MOD
for x in neg[:j]: r = r * x % MOD
print(r)
