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<iostream>
#include<algorithm>
int main(){
	int N,K;
	std::cin>>N>>K;
	long* A=new long[N];
	for (int i=0; i<N; i++){
		std::cin>>A[i];
	}
	std::sort(A,A+N);
	long ans=1;
	int prev=0,back=N-1;
	int flag=1;
	if(K%2==1){
		ans*=A[back];
		K--;
		ans%=1000000007;
		if(A[back]<0){
			flag*=-1;
			ans+=1000000007;
		}
		back--;
	}
	while(K>=1){
		if((flag*(long long)A[prev]*A[prev+1])>(flag*(long long)A[back]*A[back-1])){
			ans*=A[prev]*A[prev+1]%1000000007;
			if(A[prev]*A[prev+1]<0)flag*=-1;
			K-=2;
			prev+=2;
		}else{
			ans*=A[back]*A[back-1]%1000000007;
			if(A[back]*A[back+1]<0)flag*=-1;
			K-=2;
			back-=2;
		}
		ans%=1000000007;
		if(ans<0)ans+=1000000007;
	}
	std::cout<<ans;
	return 0;
}
