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
// Problem : E - Multiplication 4
// Contest : AtCoder - AtCoder Beginner Contest 173
// URL : https://atcoder.jp/contests/abc173/tasks/abc173_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
 
#include<bits/stdc++.h>
#include<set>
#define lli long long int
#define ma 1000000007
using namespace std;
int main()
{
	lli n,k,i,ans=1;
	cin>>n>>k;
	lli a[n];
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	if(k&1&&a[n-1]==0){
		cout<<"0";
		return 0;
	}
	if(k&1&&a[n-1]<0){
		for(i=n-1;i>=n-k;i--){
			ans=(ans*a[i])%ma;
			if(ans<0) ans+=ma;
		}
		cout<<ans;
		return 0;
	}
	lli high=n-1,low=0;
	if(k&1 && a[n-1]>0){
		ans=ans*a[n-1];
		high--;
	}
	k=k/2;
	for(i=0;i<k;i++){
		if(a[low]*a[low+1]>a[high]*a[high-1]){
			ans*=a[low];
			ans=ans%ma;
			if(ans<0) ans+=ma;
			low++;
			ans*=a[low];
			ans=ans%ma;
			if(ans<0) ans+=ma;
			low++;
		}
		else{
			ans=(ans*a[high])%ma;
			if(ans<0) ans+=ma;
			high--;
			ans=(ans*a[high])%ma;
			if(ans<0) ans+=ma;
			high--;
		}
	}
	ans=ans%ma;
	if(ans<0) ans+=ma;
	cout<<ans;
	
	return 0;
}