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>
//cervello|Phoenix
using namespace std;
#define ll long long int
#define eb emplace_back
#define mk make_pair
#define all(x) x.begin(),x.end()
#define mod 1000000007

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll n,k; cin>>n>>k;
  vector<ll> a(n); int pos=0;
  for(int i=0;i<n;i++){
  	cin>>a[i];
  	if(a[i]>=0)
  		pos++;
  }
  ll ans=1;
  sort(all(a));
  int l=0, r=n-1;
  if(pos==0&&k%2){
  	while(k){
  		while(a[r]<0)
  			a[r]+=mod;
  		ans=((ans%mod)*(a[r]%mod))%mod;
  		r--;
  		k--;
  	}
  	cout<<ans<<"\n";
  	return 0;
  }
  while(k){
  	if(k%2){
  		while(a[r]<0)
  			a[r]+=mod;
  		ans=((ans%mod)*(a[r]%mod))%mod;
  		r--;
  		k--;
  	}
  	else{
  		ll v1=a[l]*a[l+1];
  		ll v2=a[r]*a[r-1];
  		if(v1>v2){
  			while(v1<0)
  				v1+=mod;
  			ans=((ans%mod)*(v1%mod))%mod;
  			l+=2;
  		}
  		else{
  			while(v2<0)
  				v2+=mod;
  			ans=((ans%mod)*(v2%mod))%mod;
  			r-=2;
  		}
  		ans%=mod;
  		k-=2;
  	}
  }
  cout<<ans<<"\n";
  return 0;
}