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 int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<(n);i++)
#define init(a,i) for(int k=0;k<(i);k++)(a)[k]=0
#define in(a,i) for(int k=0;k<(i);k++)cin>>(a)[k]
#define all(a)  (a).begin(),(a).end()
#define el(a) (a).end()-(a).begin()
int main(){
	int n,k;
	cin>>n>>k;
	vector<ll> p,m;
	ll a[n];
	rep(i,n){
		cin>>a[i];
		if(a[i]>0)p.push_back(a[i]);
		else m.push_back(a[i]);
	}
	ll max=1;
	//すべて
	if(n==k){
		rep(i,k)max=(max*a[n-1-i])%1000000007;
		if(max<0)max=max+1000000007;
		cout << max;
		return 0;
	}
	
	
	p.push_back(0);
	m.push_back(0);
	sort(all(p));
	sort(all(m));
	
	
	ll b,c;
	int i,j;
	i=el(p)-1;
	j=0;
	
	//負となるとき(すべてが負の数)
	if(i==0&&k%2==1){
		rep(i,k)max=(max*m[el(m)-2-i])%1000000007;
		if(max<0)max=max+1000000007;
		cout<<max;
		return 0;
	}
	//絶対値が大きい順に取っていく
	rep(o,k){
		if(p[i]>-1*m[j])i--;
		else j++;
	}
	//負になるとき
	if(j%2==1){
		if(i!=el(p)-1)b=p[i+1]*p[i];
		else b=1000000000000000001;
		c=m[j-1]*m[j];
		if(b>c){
			i--;
			j--;
		}
		else{
			i++;
			j++;
		}
	}
	rep(n,j)max=(max*m[n])%1000000007;
	for(int n=el(p)-1;n>i;n--)max=(max*p[n])%1000000007;
	if(max<0)max=max+1000000007;
	cout <<max;
	return 0;
}