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 ll;
const ll MOD = 1e9+7;

int main(){
	int n,k;
	cin >> n >> k;
	
	vector<ll> a(n);
	for(int i=0; i<n; i++) cin >> a[i];
	sort(a.begin(),a.end());

	ll ans = 1, f = 0;
	int l = 0, r = n-1;

	if(k%2){
		ans = a[r];
		r--;
		--k;
		if (ans<0) f = 1;
	}

	while(k){
		ll two = a[l]*a[l+1];
		ll one = a[r]*a[r-1];

		if(f){
			if(two>=one){
				ans = one%MOD*ans%MOD;
				r -= 2;
			}

			else{
				ans = two%MOD*ans%MOD;
				l += 2;
			}
		}

		else{
			if(two<=one){
                                ans = one%MOD*ans%MOD;
                                r -= 2;
                        }

                        else{
                                ans = two%MOD*ans%MOD;
                                l += 2;
                        }
                }

		k -= 2;
	}

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

	return 0;
}