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 Int int64_t

using namespace std;

int main() {
	constexpr Int MOD = 1e9 + 7;
	Int N, K;
	cin >> N >> K;
	vector<Int> a(N), pos, neg;
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
		if (a[i] > 0) { pos.emplace_back(a[i]); }
		if (a[i] < 0) { neg.emplace_back(abs(a[i])); }
	}

	int pos_sz = pos.size(), neg_sz = neg.size();
	if ((pos_sz + neg_sz/2*2 >= K) && (pos_sz > 0 || K % 2 == 0)) {
		sort(pos.rbegin(), pos.rend());
		sort(neg.rbegin(), neg.rend());
		Int ans = (K % 2 ? pos[0] : 1);
		vector<Int> X;
		for (int i = K % 2; i + 1 < pos_sz; i += 2) {
			X.emplace_back(pos[i] * pos[i + 1]);
		}
		for (int i = 0; i + 1 < neg_sz; i += 2) {
			X.emplace_back(neg[i] * neg[i + 1]);
		}
		sort(X.rbegin(), X.rend());
		for (int i = 0; i < K / 2; ++i) { (ans *= X[i] % MOD) %= MOD; }
		cout << ans % MOD << endl;
	} else {
		for (int i = 0; i < N; ++i) { a[i] = abs(a[i]); }
		sort(a.begin(), a.end());
		Int ans = 1;
		for (int i = 0; i < K; ++i) { (ans *= a[i]) %= MOD; }
		cout << (MOD - ans) % MOD << endl;
	}

	return 0;
}
