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;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 200010;
const int INF = INT_MAX/2;
const int mod = 1e9 + 7;

int n, k;
int A[maxn];

void mul(int &a, int b) {
	a *= b;
	if (a < 0) a += mod;
	a %= mod;
}

int32_t main(){
	FAST
	//ifstream cin("random_max01.txt");
	cin >> n >> k;
	
	for (int i =0;i<n;i++) {
		cin >> A[i];
	}

	sort(A,A+n);
	int ans = 1;

	if (A[n-1] <= 0 and k % 2 == 1) {
		for (int i =n-1; i > n-1-k; i--) {
			mul(ans,A[i]);
		}
		//ans = (ans + mod) % mod;
		cout << ans;
		return 0;
	}
	
	int l = 0, r = n-1;
	
	if (k % 2 == 1) {
		mul(ans,A[r]);
		r--;
		k--;
	}
	
	for (int x = 0; x < k / 2; x++) {
		int lowest = A[l] * A[l+1], highest = A[r] * A[r-1];
		if (lowest > highest) {
			mul(ans,lowest%mod);
			l += 2;
		} else {
			mul(ans,highest%mod);
			r -= 2;
		}
		ans = (ans + mod) % mod;
	}

	cout << ans%mod;
	
}







