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<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int n,k;cin>>n>>k;
  vector<int> a(n);
  rep(i,n)cin>>a[i];
  sort(a.begin(),a.end());
  int hu=0;
  bool zero=false;
  rep(i,n){
    if(a[i]==0)zero=true;
  }
  rep(i,n){
    if(a[i]<0)++hu;
    else break;
  }
  int num=0;
  int cur=n-k;
  int res=1;
  while(num<=hu){
    if(cur+1>=n)break;
    if(a[num]*a[num+1]<a[cur]*a[cur+1]){
      break;
    }
    num+=2;
    cur+=2;
  }
  rep(i,num){
    res*=a[i];res%=MOD;
  }
  for(int i=cur;i<n;++i){
    res*=a[i];res%=MOD;
  }
  if(a[n-1]<0&&k%2==1){
    if(zero)res=MOD-1;
    else{
      res=1;
      rep1(i,k){
        res*=-a[n-i];res%=MOD;
      }
      res=MOD-res;
    }
  }
  res+=MOD;
  res%=MOD;
  cout<<res<<"\n";
  return 0;
}
