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;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
constexpr int MX = 200005, MOD = 1e9+7;
int n, k, a, ps, ns;
ll ans = 1, as[MX], rp = MOD, rn = MOD, lp = MOD, ln = MOD;
ll inv(ll a){
	ll ret = 1;
	for(int t = MOD-2; t; t /= 2, (a *= a) %= MOD){
		if(t&1) (ret *= a) %= MOD;
	}
	return ret;
}
int main(){
	scanf("%d%d", &n, &k);
	rep(i,n){
		scanf("%lld", as+i);
		if(as[i] > 0) ps++;
	}
	sort(as, as+n, [](ll a, ll b){return abs(a) < abs(b);});
	if(n == k || ((k & 1) && ps == 0)){
		rep(i,k) (ans *= as[i]) %= MOD;
		if(ans < 0) ans += MOD;
		printf("%lld\n", ans);
		return 0;
	}
	rep(i,k){
		(ans *= as[n-1-i]) %= MOD;
		if(as[n-1-i] <= 0){
			ns++;
			rn = as[n-1-i];
		}else rp = as[n-1-i];
	}
	rep(i,n-k) (as[i] <= 0 ? ln : lp) = as[i];
	if(ns & 1){
		if(ln == MOD || rp == MOD || (lp != MOD && ln * rn < lp * rp)){
			ln = lp; rp = rn;
		}
		(ans *= ln) %= MOD;
		(ans *= inv(rp)) %= MOD;
	}
	if(ans < 0) ans += MOD;
	printf("%lld\n", ans);
}