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 int
int mod=1e9+7;
int32_t main(){
    int n,k,ans=1,pos=0,neg=0,z=0,t,ok=1,s=1,e,i;
    cin>>n>>k;
    int a[n+1];
    vector<int>vpos,vneg;
    for(i=1;i<=n;i++){cin>>a[i];
        if(a[i]>0){pos++;}
        if(a[i]<0)neg++;
        if(a[i]==0)z++;
    }
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    if(n==k){
        for(i=1;i<=n;i++){ans*=a[i];ans%=mod;}
        ans=(ans+mod)%mod;
        cout<<ans;return 0;
    }
    if(!neg){
        for(i=1;i<=k;i++){ans*=a[i];ans%=mod;}
        cout<<ans;
        return 0;
    }
    t=min(k,neg);
    if(t%2)t--;
    if(t+pos<k)ok=0;
    if(!ok&&z){cout<<"0";return 0;}
if(!ok){
    for(i=1;i<=k;i++){ans*=a[i];ans%=mod;}
    ans=(ans+mod)%mod;
    cout<<ans;return 0;
}s=1;
 if(k%2){
     ans=a[1];
     k--;
     s=2;
 } e=n;
 while(k){
     if(a[s]*a[s+1]>a[e]*a[e-1]){
         ans*=a[s];
         ans%=mod;
         ans*=a[s+1];ans%=mod;
         s+=2;
     }else{
         ans*=a[e];
         ans%=mod;
         ans*=a[e-1];
         ans%=mod;
         ans=(ans+mod)%mod;
         e-=2;
     }
     k-=2;
 }
 cout<<ans;
    return 0;
}