80pts

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005,dajiba=1e9+9;
int ans=1,n,k,a[N]; 
int ju=1;//-1=-,1=+
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	if(k%2){
		k--;n--;
		ans*=a[n];
		if(ans<0) ju=-1; 
	}int l=1,r=n;k+=2;
	while(k-=2){
		int ll=a[l]*a[l+1],rr=a[r]*a[r-1];
		if(ll*ju>=rr*ju) ans=(ll%dajiba)*ans%dajiba,l+=2;
		else ans=(rr%dajiba)*ans%dajiba,r-=2;
	}
	cout<<ans%dajiba;
	return 0;
}