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 int long long
const long long MOD=1e9+7;
void f(int &a){
  a%=MOD;if(a<0)a+=MOD;
}
void kakeru(int &a,int b){
  f(a);f(b);a*=b;f(a);
}

signed main(){
  int n,k,ans=1;cin>>n>>k;
  vector<int> pl,mi;
  for(int i=0;i<n;i++){
    int a;cin>>a;
    (a>=0?pl:mi).push_back(a);
  }
  sort(pl.begin(),pl.end());
  sort(mi.begin(),mi.end());
  if(n==k){
    for(int p:pl)kakeru(ans,p);
    for(int p:mi)kakeru(ans,p);
    cout<<ans<<endl;return 0;
  }
  if(k&1)
    if(pl.size()){
      kakeru(ans,pl.back());
      pl.erase(pl.end()-1);
    }
    else{
      for(int i=0;i<k;i++)kakeru(ans,mi[n-1-i]);
      cout<<ans<<endl;return 0;
    }
  k>>=1;
  priority_queue<int> pque;
  for(int i=(int)pl.size()-1;i>0;i-=2)pque.push(pl[i]*pl[i-1]);
  for(int i=0;i<(int)mi.size()-1;i+=2)pque.push(mi[i]*mi[i+1]);
  while(k--){
    kakeru(ans,pque.top());pque.pop();
  }
  cout<<ans<<endl;
}
