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;

int main(){

	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif

	ios::sync_with_stdio(false),cin.tie(0);
	
	const long long p = 1000000007;

	long long n,k; cin>>n >>k;
	long long a[n];
	for(long long i=0;i<n;i++) cin >> a[i];
	sort(a,a+n);
	long long ans = 1;
	if(k%2 == 1){
		if(a[n-1] == 0) {cout << 0 << endl; return 0;}
		if(a[n-1]<0){

			for(long long i=0;i<k;i++){
				ans = ((ans%p)*a[n-1-i])%p;
			ans = (p+ans%p)%p;
			}
			cout << (p+ans%p)%p << endl;
			return 0;
		}

		ans = a[n-1];
		n--;
	}

	k = k/2;

	long long i=0; long long j=n-2;

	while(k>0){
		if(a[i]*a[i+1]>a[j]*a[j+1]){
			ans = ((ans%p)*(a[i]%p))%p;
			ans = ((ans%p)*(a[i+1]%p))%p;
			ans = (p+ans%p)%p;
			i+=2;
		}
		else{
			ans = ((ans%p)*(a[j]%p))%p;
			ans = ((ans%p)*(a[j+1]%p))%p;
			ans = (p+ans%p)%p;
			j-=2;
		}

		k--;
	}

	cout << (p+ans%p)%p << endl;

	return 0;
}