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 int N = 2e5 + 10;
const int mod = 1e9 + 7;

int a[N], ac;
int b[N], bc;

int main (void) {
	int k, n;
	scanf("%d%d", &n, &k);
	for (int i = 1, x; i <= n; i ++) {
		scanf("%d", &x);
		if (x < 0)
			a[++ ac] = -x;
		else 
			b[++ bc] = x;
	}
	sort(a + 1, a + ac + 1);
	sort(b + 1, b + bc + 1);
	if (n == k) {
		long long res = 1;
		for (int i = 1; i <= ac; i ++)
			res = res * a[i] % mod;
		for (int i = 1; i <= bc; i ++)
			res = res * b[i] % mod;
		if (ac & 1) {
			res = - res;
			if (res < 0)
				res += mod;
		}
		printf("%lld\n", res);
	} else if ((k & 1) && bc == 0) {
		long long res = 1;
		for (int i = 1; i <= k; i ++)
			res = res * a[i] % mod;
		res = - res;
		if (res < 0)
			res += mod;
		printf("%lld\n", res);
	} else {
		long long res = 1;
		if (k & 1) {
			k --;
			res = res * b[bc --] % mod;
		}
		while (k > 0) {
			if ((ac >= 2 && bc >= 2 && 1ll * a[ac] * a[ac - 1] >= 1ll * b[bc] * b[bc - 1])
				|| (ac >= 2 && bc < 2)) {
				res = res * a[ac --] % mod;
				res = res * a[ac --] % mod;
			} else {
				res = res * b[bc --] % mod;
				res = res * b[bc --] % mod;
			}
			k -= 2;
		}	
		printf("%lld\n", res);
	}
}