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;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll INF = 1LL << 60; //MAX 9223372036854775807

ll ans = 1;
const ll mo = 1000000007;
auto mod = [](ll modx) {modx%=mo;modx+=mo;modx%=mo;return modx; };

int main()
{
ll n , k ;
cin >> n >> k ;
vector<ll> a(n);
rep(i, n){
  cin >> a[i];
}
sort(a.begin(),a.end());
if(n==k){
  ll b=1;
  rep(i,n)b=mod(b*a[i]);
  cout << b << endl;
  return 0;
}
if(a[n-1]<0&&k%2){
  ll b=1;
  rep(i,k)b=mod(b*a[n-1-i]);
  cout << b << endl;
  return 0;
}
vector<ll> s;
vector<ll> f;
rep(i,n){
  if(a[i]<0)f.push_back(-a[i]);
  else s.push_back(a[i]);
}
sort(f.begin(),f.end());
sort(s.begin(),s.end());
reverse(f.begin(),f.end());
reverse(s.begin(),s.end());
ll nums=0,numf=0;
if(k%2){ans=s[0];nums++;}
while(k>numf+nums){
  if(nums+1<s.size()&&numf+1<f.size()){
    if(s[nums]*s[nums+1]>f[numf]*f[numf+1]){ans=mod(ans*mod(s[nums]*s[nums+1]));nums+=2;}
    else{ans=mod(ans*mod(f[numf]*f[numf+1]));numf+=2;}
  }
  else if(nums+1<s.size()){ans=mod(ans*mod(s[nums]*s[nums+1]));nums+=2;}
  else {ans=mod(ans*mod(f[numf]*f[numf+1]));numf+=2;}
}
cout << ans << endl;
return 0;
}