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 <algorithm>
#include <iostream>
#include <cassert>
#include <cstdio>

typedef long long lli;
#define NMAX 200010

using namespace std;

int pos[NMAX];
int neg[NMAX];
int N,K;

const int mod = (1e9+7);

int main(){
	int t,n,p,i,x,j,sl;
	lli p1,p2;

	// scanf("%d",&t);
    t = 1;

	while(t--){

		scanf("%d%d",&N,&K);

		p = n= 0;
		sl=1;
		while(N--){
			scanf("%d",&x);
			if(x < 0) neg[n++]=x;
			else pos[p++]=x;
			sl = (1LL*sl*x)%mod;
		}
		pos[p] = neg[n]=1;

		if(K >= (p+n)){
			if(sl < 0) sl+=mod;
			printf("%d\n",sl);
			continue;
		}

		sort(pos,pos+p);
		reverse(pos,pos+p);
		sort(neg,neg+n);


		if(!p && (K&1)){
			sl=1;
			i=n;
			while(K--){
				sl = (1LL*sl*neg[--i])%mod;
			}
			if(sl < 0) sl += mod;
			printf("%d\n",sl);
			continue;
		}

		i = j = 0;


		while(K){
			p1 = 1ll*pos[i]*pos[i+1];
			p2 = 1ll*neg[j]*neg[j+1];

			if(K == 1 && i >= p){
				--i;
				j += 2;
				assert(j <= n);
				--K;
				continue;
			}

			if(i >=p || (K > 1 && j < n-1 && p1 < p2)){
				assert(j < n-1);
				K-=2;
				j+=2;
				continue;
			}

			++i;
			--K;
		}

		sl = 1;
		while(i--) sl = (1LL*sl*pos[i])%mod;
		while(j--) sl = (1LL*sl*neg[j])%mod;

		assert(sl >= 0);
		printf("%d\n",sl);
	}
}
