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>
#define ll long long int
#define forr(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define oo 1000000000000000000LL
using namespace std;


void _sol(){
    int n,k; cin >> n >> k;
    vector<ll> v(n);
    forr(i,n) cin >> v[i];
    sort(v.begin(),v.end());
    ll ans = 1;
    n--;
    if(k%2){
        if( v[n] <=0 ){
            int p = n;
            while(k>0){
                ans = (ans * v[p])%mod;
                if(ans<0) ans+= mod;
                p--;
                k--;
            }
            cout << ans;
            return;
        }
        ans = (ans * v[n])%mod;
        if(ans<0) ans+= mod;
        k--;
        n--;
    }
    int i = 0;
    while(k>0){
        ll p = v[i]*v[i+1] , q = v[n]*v[n-1];
        if(p>q){
            ans = (ans * (p%mod))%mod;
            i+=2;
        }
        else{
            ans = (ans * (q%mod))%mod;
            n-=2;
        }
        k-=2;
    }
    cout << (ans+mod)%mod;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while(t--) _sol();
}
