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;
typedef pair<ll,ll> P;
const ll mod=1e9+7,INF=mod*mod*3;//M_PI
#define rep(i,N) for(ll i=0; i<(N); i++)
#define rep1(i,N) for(ll i=1; i<(N); i++)
#define pb push_back

ll N,K;
ll pos[200005];
ll neg[200005];

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N>>K;
ll p1=0;
ll n1=0;
rep(i,N){
    ll a;
    cin>>a;
    if(a>=0){
        pos[p1++]=a;
    }
    else{
        neg[n1++]=-a;
    }
}
sort(pos,pos+p1);
sort(neg,neg+n1);
if(N==K){
    ll ans=1;
    rep(i,p1) ans=ans*pos[i]%mod;
    rep(i,n1) ans=ans*(mod-neg[i])%mod;
    cout<<ans<<endl;
    exit(0);
}
if(K%2==1&&n1==N){
    ll ans=1;
    rep(i,K) ans=ans*(mod-neg[i])%mod;
    cout<<ans<<endl;
    exit(0);   
}
ll ans=1;
while(K){
    if(K>=2&&n1>=2&&(p1<=1||(p1>=2&&neg[n1-1]*neg[n1-2]>=pos[p1-1]*pos[p1-2]))){
        ans=ans*neg[--n1]%mod;
        ans=ans*neg[--n1]%mod;
        K-=2;
    }
    else{
        ans=ans*pos[--p1]%mod;
        K--;
    }
}
cout<<ans<<endl;


}
    
