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>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
#include <stack>
#include <set>
#include <queue>
#include <list>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

void solve() {
	int n, k; cin >> n >> k;
	vector<ll> v(n);
	for (ll &i : v)cin >> i;
	sort(v.begin(), v.end());
	int l = 0, r = n - k;
	while (l < r && r < n - 1) {
		if (1ll * v[l]*v[l + 1] >= v[r]*v[r + 1] * 1ll) {l += 2; r += 2;}
		else break;
	}
	if ((k & 1) && v.back() < 0) {
		l = 0;
		r = n - k;
	}
	ll ans = 1;
	for (int i = 0; i < l; i++)ans = 1ll * ans * ((v[i] % mod) + mod) % mod;
	for (int i = r; i < n; i++)ans = 1ll * ans * ((v[i] % mod) + mod) % mod;
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// int t; cin >> t;
	// while (t--)
	solve();

}