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 <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1e9 + 7;
int n, k;
vector<ll> ps, ng;
bool z;
ll ans = 1;

void nonPositive() {
	if (z) {
		cout << 0 << endl;
	} else {
		ans = -1;
		vector<ll> abs;
		for (ll i : ps)
			abs.push_back(i);
		for (ll i : ng)
			abs.push_back(i);
		sort(abs.begin(), abs.end());
		for (int i = 0; i < k; ++i)
			ans = ans * abs[i] % mod;
		if (ans < 0)
			ans += mod;
		cout << ans << endl;
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		if (a > 0)
			ps.push_back(a);
		else if (a < 0)
			ng.push_back(-a);
		else
			z = 1;
	}

	sort(ps.begin(), ps.end(), greater<ll>());
	sort(ng.begin(), ng.end(), greater<ll>());

	vector<ll> p;
	if ((k & 1) && !ps.size()) {
		nonPositive();
		return 0;
	}

	if (k & 1)
		ans = ps[0];
	for (int i = 0; i < ps.size() / 2; ++i)
		p.push_back(ps[2 * i + (k & 1)] * ps[2 * i + 1 + (k & 1)]);

	for (int i = 0; i < ng.size() / 2; ++i)
		p.push_back(ng[2 * i] * ng[2 * i + 1]);
	if (k / 2 > p.size()) {
		nonPositive();
		return 0;
	}

	sort(p.begin(), p.end(), greater<ll>());
	for (int i = 0; i < k / 2; ++i)
		ans = ans * (p[i] % mod) % mod;
	cout << ans << endl;
}
