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
#include <iostream>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
int upll(const void*a, const void*b) { 
	return*(ll*)a<*(ll*)b ? -1 : *(ll*)a>*(ll*)b ? 1 : 0; 
}
void sortup(ll*a, int n) { 
	qsort(a, n, sizeof(ll), upll); 
}
#define MOD 1000000007
ll m[200010], p[200010];
int mm_c, p_c;
int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	rep(i, 0, n) {
		int t;
		scanf("%d", &t);
		if (t >= 0)p[p_c++] = t;
		else m[mm_c++] = -t;
	}
	sortup(m, mm_c);
	sortup(p, p_c);
	if (q == n) {
		ll ans = 1;
		rep(i, 0, mm_c)ans = ans * (MOD - m[i]) % MOD;
		rep(i, 0, p_c)ans = ans * p[i] % MOD;
		printf("%lld", ans);
		return 0;
	}
	if (q % 2 == 1 && mm_c == n) {
		ll ans = 1;
		rep(i, 0, q)ans = ans * (MOD - m[i]) % MOD;
		printf("%lld", ans);
		return 0;
	}
	ll ans = 1;
	while (q) {
		if (q >= 2 && mm_c >= 2 && (p_c <= 1 || (p_c >= 2 && m[mm_c - 1] * m[mm_c - 2] >= p[p_c - 1] * p[p_c - 2]))) {
			ans = ans * m[--mm_c] % MOD;
			ans = ans * m[--mm_c] % MOD;
			q -= 2;
		}
		else {
			ans = ans * p[--p_c] % MOD;
			q--;
		}
	}
	printf("%lld", ans);
}
