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() {
	int N;
	int K;
	int q;
	int q11;
	int q22;
	long long p;
	long long p1;
	long long p2;
	long long p3;
	long long p4;
   
	cin >> N >> K;
	int a[N];
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
    sort(a, a + (N), greater<int>());  // a[0:N] を大きい順にソート
  	if (K==1){
		cin >> a[0];
 		p=1000000007;
      	p+=a[0];
		p=p%1000000007;
		cout << p << endl;
      return 0;
    }
	if (((K%2)==1)&&(a[0]<=0)){
		p=1;
		for(int i=0;i<K;i++){
			p*=a[i];
			p=p%1000000007;
		}
		p+=1000000007;
		p=p%1000000007;
		cout << p << endl;
		return 0;
	}
	q=0;
	q11=(K%2);
	q22=N-1;
	for(int i=(K%2);i<K;i++){
		if(a[q11]>-a[q22]) {
			q11++;
		} else {
			q22--;
			q++;
		}
	}
 	if ((q%2)==1){
 		p1=a[q11-1];
		p2=a[q11];
		p3=a[q22];
		p4=a[q22+1];
		if(p1*p2<p3*p4) {
			q11--;
			q22--;
		} else {
			q11++;
			q22++;
		}
	}
  	p=1;
	while (q11 > 0) {
		q11--;
		p*=a[q11];
		p=p%1000000007;
	}
	while (q22 < N-1) {
		q22++;
		p*=a[q22];
		p=p%1000000007;
	}
	p+=1000000007;
	p=p%1000000007;
	cout << p << endl;
	return 0;
}
