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;
using ll = long long;
const ll mod = 1e9+7;
ll a[200005];
ll n,k;
int main(){
	//freopen("in.txt","r",stdin);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int L = 0,R = n-1;
	if(k&1){
		if(a[n-1] < 0){
			ll ans = 1;
			for(int i=n-1;i>=n-k;i--){
				ans *= a[i];
				ans %= mod;
			}
			if(ans < 0) cout<<ans+mod<<endl;else cout<<ans<<endl;
			exit(0);
		}
		
		R--,k--;
	}
	while(k){
		ll lv = a[L] * a[L+1];
		ll rv = a[R] * a[R-1];
		
		if(lv < rv){
			R -= 2;
		}	else L += 2;
		k -= 2;
	}
	ll ans = 1;
	for(int i=0;i<L;i++){
		ans *= a[i];
		ans %= mod;
	}
	for(int i=R+1;i<n;i++){
		ans *= a[i];
		ans %= mod;
	}
	if(ans < 0) cout<<ans+mod<<endl;
	else cout<<ans<<endl;
	return 0;
}






