#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,ft=0,tnt=1,a[114514];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<0)ft++;
	}
	sort(a+1,a+n+1);
	if(ft<2){
		for(int i=n;i>=n-m+1;i--){
			tnt*=a[i];
			if(abs(tnt)>1000000009)tnt%=1000000009;
		}
	}
	else{
		int le=1,ri=n;
		if(m%2==1){
			tnt=a[n];
			m--;
			ri--;
		}
		for(int i=1;i<=m/2;i++){
			if(a[le]*a[le+1]>a[ri]*a[ri-1]){
				tnt*=a[le]*a[le+1];
				if(abs(tnt)>=1000000009)tnt%=1000000009;
				le+=2;
				//cout<<tnt<<" le"<<endl;
			}
			else{
				tnt*=a[ri]*a[ri-1];
				if(abs(tnt)>=1000000009)tnt%=1000000009;
				ri-=2;
				//cout<<tnt<<" ri"<<endl;
			}
			
		}
		
	}
	
	cout<<tnt;
	return 0;
}