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 int M=1000000007;
signed main(){
  int N,K;
  cin>>N>>K;
  vector<int> A(N);
  for(int &i:A)
    cin>>i;
  sort(A.begin(),A.end());
  if(A[N-1]<=0){
    int ans=1;
    if(K%2==1){
      for(int i=0;i<K;i++)
        ans=(ans*A[N-1-i]%M+M)%M;
    }else{
      for(int i=0;i<K;i++)
        ans=(ans*A[i]%M+M)%M;
    }
    cout<<ans<<endl;
    return 0;
  }
  int l=0,r=N-1,ans=1;
  for(int i=0;i<K;i++){
    if(i==K-3 && A[r]<0){
    }if(A[r]*A[r-1]>=A[l]*A[l+1] || A[r]>=A[l]*A[l+1]){
      ans=(ans*A[r]%M+M)%M;
      r--;
    }else if(i==K-1){
      ans=(ans*A[r]%M+M)%M;
    }else{
      ans=((ans*A[l]%M+M)%M*A[l+1]%M+M)%M;
      l+=2;
      i++;
    }
  }
  cout<<ans<<endl;
}