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
#define pii pair<int,int>
#define PI 2*acos(0)
#define INF 1e17
#define mx 2*1000000+5
using namespace std;
const ll int p=1000000007;
ll int mod(ll int a,ll int b)
{
    ll int m=a%b;
    if(m<0) m=(b<0)?(m-b):(m+b);
    return m;
}
ll int pro(ll int a[],ll int n,ll int k)
{
    ll int it,res=1,i,j,left,right;
    sort(a,a+n);
    if(a[n-1]==0 && k%2==1) return 0;
    if(a[n-1]<0 && k%2==1){
        for(i=n-1;i>=n-k;i--){
            res*=mod(a[i],p);
            res=mod(res,p);
        }
        return res;
    }
    i=0;j=n-1;
    if(k%2){
        res*=mod(a[j],p);
        res=mod(res,p);
        j--;
        k--;
    }
    k/=2;
    for(it=0;it<k;it++){
        left=a[i]*a[i+1];
        right=a[j]*a[j-1];
        if(left>=right){
            res*=mod(left,p);
            res=mod(res,p);
            i+=2;
        }
        else{
            res*=mod(right,p);
            res=mod(res,p);
            j-=2;
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll int i,j,n,k;
    cin>>n>>k;
    ll int a[n];
    for(i=0;i<n;i++) cin>>a[i];
    cout<<pro(a,n,k)<<endl;
    return 0;
}
