#include<bits/stdc++.h>
using namespace std;
const int mod=1000000009;
typedef  long long ll;
int a[100010];
int n,k,sign=1,l,r;
ll ans=1;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    l=1,r=n;
    if(k&1){
        ans=a[n];
        r--;
        k--;
        if(ans<0)sign=-1;
    }
    while(k){
        ll x=1ll*a[l]*a[l+1];
        ll y=1ll*a[r]*a[r-1];
        if(x*sign>y*sign)l+=2,k-=2,ans=x%mod*ans%mod;
        else r-=2,k-=2,ans=y%mod*ans%mod;

    }
    cout<<ans;
}