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;

const int64_t MOD = 1e9+7;

void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int main() {
	// your code goes here
	int n, k;
	int64_t ans = 1;
	cin >> n >> k;
	vector<int64_t> a, b, A;
	for(int i = 0; i < n; ++i){
		int64_t l;
		cin >> l;
		A.push_back(abs(l));
		if(l < 0)b.push_back(abs(l));
		else if(l > 0) a.push_back(abs(l));
	}
	
	int szn = b.size(), szp = a.size();
	
	if((szp + szn/2*2 >= k) && (k%2 == 0 || szp > 0)){
		sort(a.rbegin(), a.rend());
        sort(b.rbegin(), b.rend());
		if(k%2)ans = a[0];
		vector<int64_t> V;
		for(int i=k%2; i+1<szp; i+=2) V.push_back(a[i]*a[i+1]);
        for(int i=0; i+1<szn; i+=2) V.push_back(b[i]*b[i+1]);
        sort(V.rbegin(), V.rend());
        for(int i=0; i<k/2; i++) mul(ans, V[i] % MOD);
	}
	else{
		sort(A.begin(), A.end());
        for(int i=0; i<k; i++) mul(ans, A[i]);
        ans = (MOD-ans) % MOD;
	}
	
	cout << ans << endl;
	return 0;
}