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;
typedef long long ll;
#define faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define mod ll(1e9+7)

int main()
{
	faster;
	
	ll n,k;
	cin >> n >> k;

	vector<ll> a(n);

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

	sort(a.begin(),a.end());

	ll res = 1,sign = 1,left = 0,right = n-1;

	if(k % 2)
	{
		res = (a[right--]%mod);
		res %= mod;
		if(res < 0)
		{
			sign = -1;
		}
		k--;
	}
	while(k)
	{
		ll x = a[left] * a[left+1], y = a[right] * a[right-1];
		if(x * sign > y * sign)
		{
			res *= (x % mod);
			res %= mod;
			left += 2;
		}
		else 
		{
			res *= (y % mod);
			res %= mod;
			right -= 2;
		}
		k -= 2;
	}
	cout << ((mod+res) % mod)<< endl;
	
	return 0;
}
