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>
#define rep(i,n) for(ll i = 0; i < (ll)(n); ++i)

using namespace std;
using ll = long long;

int main() {
	const ll mod = 1000000007;
	ll x, k, ans = 1;
	bool plus = false;
	cin >> x >> k;
	if (x == k) {
		ll a;
		rep(i, x) {
			cin >> a;
			ans = ans * a % mod;
			if (ans < 0) ans += mod;
		}		
		cout << ans << endl;
		return 0;
	}
	if (k % 2 == 0) plus = true;
	vector<ll> p, n;
	rep(i, x) {
		ll a;
		cin >> a;
		if (a >= 0) p.push_back(a);
		else n.push_back(a);
		if (a >= 0 && !plus) plus = true;
	}
	sort(p.rbegin(), p.rend());
	sort(n.begin(), n.end());
	if (plus) {
		int ip = 0, in = 0;
		if (k % 2) {
			ans *= p[0];
			ip++;
			k--;
		}
		while (k) {
			ll pos = 0, neg = 0;
			if (ip + 1 < (int)p.size()) {
				pos = p[ip] * p[ip + 1];
			}
			if (in + 1 < (int)n.size()) {
				neg = n[in] * n[in + 1];
			}
			if (pos >= neg) {
				ans = ans * (pos % mod) % mod;
				ip += 2;
				k -= 2;
			}
			else {
				ans = ans * (neg % mod) % mod;
				in += 2;
				k -= 2;
			}
		}
	}
	else {
		ll i = n.size() - 1;
		while (k) {
			ans = ans * n[i] % mod;
			i--;
			k--;
		}
	}
	if (ans < 0) ans += mod;
	cout << ans << endl;
	return 0;
}
