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<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int N_MAX = 200000;
ll p=1e9+7;
int main()
{
  int n,k,i,j,aa,bb,f;
  ll t,res=1;
  vector<ll> a,b;
  cin >> n >> k;
  for(i=0;i<n;i++){
    cin >> t;
    if(t>=0)
      a.push_back(t);
    else
      b.push_back(-t);
  }
  aa=a.size();
  bb=b.size();
  sort(a.begin(),a.end(),greater<ll>());
  sort(b.begin(),b.end(),greater<ll>());
  if(aa>0||k%2==0){
    i=min(aa,k);
    if((k-i)%2==1&&n>k&&i>0)
      i--;
    j=k-i;
    while(i>=2&&j<=bb-2){
      if(a[i-1]*a[i-2]<b[j]*b[j+1]){
        i-=2;
        j+=2;
      }else{
        break;
      }
    }
    f=j%2;
    for(i--;i>=0;i--){
      res*=a[i];
      res%=p;
    }
    for(j--;j>=0;j--){
      res*=b[j];
      res%=p;
    }
  }else{
    f=1;
    for(j=bb-1;j>=bb-k;j--){
      res*=b[j];
      res%=p;
    }
  }
  if(f==1) 
    res=p-res;
  cout << res << endl;
  return 0;
}