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 lli long long int
#define mod 1000000007

int main()
{
	lli n,k,res=1;
	cin>>n>>k;
	vector<lli> v(n);
	for(lli i=0;i<n;i++)
	cin>>v[i];
	sort(v.begin(),v.end(),greater<lli>());
	if(k==n||(v[0]<0&&k%2==1))
	{
		for(lli i=0;i<k;i++)
		res=(res*(v[i]+mod)%mod+mod)%mod;
	}
	else
	{
		lli lo=0,hi=n-1,cnt=0;
		if(k%2)
		{
			res=(res*v[lo])%mod;
			cnt++;
			lo++;
		}
		while(cnt<k)
		{
			//if(k-cnt>=2)
			//{
				if(v[lo]*v[lo+1]>=v[hi]*v[hi-1])
				res=(res*(v[lo]%mod*v[lo+1]%mod)%mod)%mod,lo=lo+2;
				else
				res=(res*((v[hi]+mod)%mod*(v[hi-1]+mod)%mod)%mod)%mod,hi=hi-2;
				cnt=cnt+2;
			//}
			/*else
			{
				if(res*v[lo]>=res*v[hi])
				res=(res*v[lo]+mod)%mod,lo++,cnt++;
				else
				res=(res*v[hi]+mod)%mod,hi--,cnt++;
			}*/
		}
	}
	cout<<res<<endl;
	return 0;
}
