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 <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

const long long mod = 1000000007;
vector<long long> pos, neg; int zero;

int main()
{
	int n, k; scanf ("%d %d", &n, &k);
	for (int i = 0; i < n; i++){
		int x; scanf ("%d", &x);
		if (x > 0) pos.push_back(x);
		else if (x < 0) neg.push_back(-x);
		else zero++;
	}

	if (pos.size() + neg.size() < k){
		puts("0");
		return 0;
	}

	sort(pos.rbegin(), pos.rend());
	sort(neg.rbegin(), neg.rend());

	int i = 0, j = 0;
	while (i + j < k){
		if (j == neg.size() || i < pos.size() && pos[i] > neg[j]) i++;
		else j++;
	}

	if (j % 2){
		long long u1 = 0, v1 = 1;
		long long u2 = 0, v2 = 1;
		
		if (i < pos.size() && j > 0) u1 = pos[i], v1 = neg[j - 1];
		if (i > 0 && j < neg.size()) u2 = neg[j], v2 = pos[i - 1];
		if (u1 || u2){
			if (u1 * v2 > v1 * u2) i++, j--;
			else i--, j++;
		}
	}

	long long a = 1;
	if (j % 2){
		sort(pos.begin(), pos.end());
		sort(neg.begin(), neg.end());
	}
	for (int p = 0; p < i; p++) a = a * pos[p] % mod;
	for (int n = 0; n < j; n++) a = a * (mod - neg[n]) % mod;
	if (j % 2 && zero) a = 0;

	printf ("%lld\n", a);
	return 0;
}