#include<iostream>
#include<algorithm>
#define int unsigned long long
using namespace std;

const int N = 1e6+10,mod=1e9+9;

int w[N];
int n,m;

signed main(){
    cin>>n>>m;
    int p=1;//判断正负
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    sort(w+1,w+1+n);
    
    int ans;
    if(m%2){
        ans=w[n];
        n--;
        m--;
        if(ans<0)p=-1;
    }
    int l=1,r=n;
    while(m){
        if(w[l]*w[l+1]*p>=w[r]*w[r-1]*p){
            ans=w[l]*w[l+1]%mod*ans%mod;
            l+=2;
        }else{
            ans=w[r]*w[r-1]%mod*ans%mod;
            r-=2;
        }
        m-=2;
    }
    cout<<ans;
    
    return 0;
}