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>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;

const int m = 1000000007;

int print(ll ans){
  ans%=m;
  if(ans<0) ans+=m;
  cout << ans << "\n";
  return 0;
}

int main(){
  int n,k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  sort(a.rbegin(),a.rend());
  ll ans=1;
  if(a[0]<0){
    if(k%2==1){
    rep(i,k){ans*=a[i];ans%=m;}
    print(ans);
    return 0;
    }else{
    rep(i,k){ans*=a[n-1-i];ans%=m;}
    print(ans);
    return 0;
    }
  }
  int index1=0,index2=n-1;
  if(k%2==1){
    ans*=a[0];
    k--;
    index1++;
  }
  rep(i,k/2){
    if(a[index1]*a[index1+1]>a[index2]*a[index2-1]){
      ans*=a[index1];ans%=m;
      ans*=a[index1+1];ans%=m;
      index1+=2;
    }else{
      ans*=a[index2];ans%=m;
      ans*=a[index2-1];ans%=m;
      index2-=2;
    }
  }
  print(ans);
  return 0;
}