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;
const ll mod= 1e9+7;

bool cmp(ll &a, ll &b){
	return abs(a)>abs(b);
}

int main(){
	int n,k;
	cin>>n>>k;
	vector<ll>v(n);
	for(ll &x:v){
		cin>>x;
	}	
	sort(v.begin(),v.end(),cmp);

	int negs=0;
	for(int i=0;i<k;i++){
		negs+=(v[i]<0);
	}
	if(negs%2==1){
		
		int c1=-1,c2=-1,d1=-1,d2=-1;

		for(int i=0;i<k;i++){
			if(v[i]<0)c1=i;
			if(v[i]>=0)d1=i;
			
		}
		for(int i=k;i<n;i++){
			if(v[i]>=0 && c2==-1)c2=i;
			if(v[i]<0 && d2==-1)d2=i;
		}
		
		if(c1!=-1 && c2!=-1 && d1!=-1 && d2!=-1){
			if(v[c1]*v[d2]< v[c2]*v[d1]){
				swap(v[c1],v[c2]);
			}else{
				swap(v[d1],v[d2]);
			}
		}else if(c1!=-1 && c2!=-1){
			swap(v[c1],v[c2]);
		}else if(d1!=-1 && d2!=-1){
			swap(v[d1],v[d2]);
		}else{
			reverse(v.begin(),v.end());
		}
	}

	ll ret= 1;
	for(int i=0;i<k;i++){
		ret*=v[i];
		ret%=mod;
	}
	//cout<<'\n';
	ret=(mod+ret)%mod;
	cout<<ret<<'\n';
	return 0;
}