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;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i,n) for(UL i=0; i<(n); i++)

const ULL M=1000000007;

ULL MSign(LL a){
 if(a<0) return M-((-a-1)%M)-1;
 return a%M;
}

int main() {
 UL N,K; scanf("%u%u",&N,&K);
 deque<LL> A[2];
 rep(i,N){
  LL a; scanf("%lld",&a);
  A[(a<=0)?0:1].push_back(a);
 }
 sort(A[0].begin(),A[0].end());
 sort(A[1].begin(),A[1].end());
 ULL ans=1;
 if(A[1].empty()){
  if(K%2==1) reverse(A[0].begin(),A[0].end());
  rep(k,K) ans=ans*MSign(A[0][k])%M;
 }
 else if(N==K){
  rep(i,2) for(LL a:A[i]) ans=ans*MSign(a)%M;
 }
 else{
  if(K%2==1){ ans=MSign(A[1].back()); N--; K--; A[1].pop_back(); }
  reverse(A[1].begin(),A[1].end());
  if(A[0].size()%2==1){ N--; A[0].pop_back(); }
  if(A[1].size()%2==1){ N--; A[1].pop_back(); }
  rep(i,A[0].size()){ A[0].push_back(A[0][0]*A[0][1]); rep(j,2)A[0].pop_front(); }
  rep(i,A[1].size()){ A[1].push_back(A[1][0]*A[1][1]); rep(j,2)A[1].pop_front(); }
  rep(k,K/2){
   UL c=0;
   if(A[0].empty()) c=1;
   if(A[0].size() && A[1].size()) if(A[0][0]<A[1][0]) c=1;
   ans = ans*(MSign(A[c][0]))%M;
   A[c].pop_front();
  }
 }
 printf("%llu\n",ans);
 return 0;
}

