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 ll long long 
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define MOD 1000000007

ll mul(ll a, ll b) {
	ll x = (a * b) % MOD;
	if(x < 0) return x + MOD;
	return x;
}

ll maxProductSubarrayOfSizeK(ll A[], ll n, ll k) 
{  
	sort(A, A + n); 
	ll product = 1; 
	if (A[n - 1] == 0 && (k & 1)) 
		return 0; 
	if (A[n - 1] <= 0 && (k & 1)) { 
		for (ll i = n - 1; i >= n - k; i--) 
			product = mul(product, A[i]); 
		return product; 
	} 
	ll i = 0; 
	ll j = n - 1; 
	if (k & 1) { 
		product = mul(product, A[j]);
		j--; 
		k--; 
	} 
	k >>= 1;  
	for (ll itr = 0; itr < k; itr++) { 
		ll left_product = A[i] * A[i + 1]; 
		ll right_product = A[j] * A[j - 1]; 
		if (left_product > right_product) { 
			product = mul(product, left_product % MOD);
			i += 2; 
		} 
		else { 
			product = mul(product, right_product % MOD);
			j -= 2; 
		} 
	} 
	return product; 
} 

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	ll n, k; cin >> n >> k;
	ll a[n];
	for(ll i = 0; i < n; i++)
		cin >> a[i];

	cout << maxProductSubarrayOfSizeK(a, n, k);

	return 0;
}