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<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=1e6+5;
const ll mod=1e9+7;
vector<ll> neg,pos;
int main() {
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) {
        int tem;cin>>tem;
        if(tem>0) pos.push_back(tem);
        if(tem<0) neg.push_back(tem);
    }
    bool ok=0;int mn=0;
    sort(neg.begin(),neg.end());
    sort(pos.begin(),pos.end(),greater<int>());
    for(int i=0;i<=neg.size()&&i<=k;i+=2)
        if(pos.size()+i>=k) {
            ok=1;mn=i;break;
        }
    ll ans=1;
    if(!ok) {
        if(pos.size()+neg.size()<n) {cout<<0<<endl;return 0;}
        sort(neg.begin(),neg.end(),greater<int>());
        for(int i=0;i<min(k,(int)neg.size());i++) (ans*=neg[i])%=mod;
        sort(pos.begin(),pos.end());
        for(int i=0;i<k-(int)neg.size();i++) (ans*=pos[i])%=mod;
    }
    else {
        for(int i=mn+2;i<=neg.size()&&i<=k;i+=2) {
            if(neg[i-1]*neg[i-2]>pos[k-i]*pos[k-i+1]) mn=i;
                else break;
        }
        for(int i=0;i<mn;i++) (ans*=neg[i])%=mod;
        for(int i=0;i<k-mn;i++) (ans*=pos[i])%=mod;
    }
    (ans+=mod)%=mod;
    cout<<ans<<endl;
    return 0;
}