#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[100001];
int cnt[3];
long long ans=1;
bool cmp(int a,int b){
	return abs(a)>abs(b);
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		if(a[i]>0){
			cnt[0]++;
		}else if(a[i]==0){
			cnt[2]++;
		}else{
			cnt[1]++;
		}
	}
	sort(a+1,a+n+1,cmp);
	if(cnt[0]==n){
		for(int i=1;i<=k;i++){
			ans=(ans%1000000009)*(a[i]%1000000009)%1000000009;
		}
	}else if(cnt[1]==n){
		if(k&1){
			for(int i=n;i>=n-k+1;i--){
				ans=(ans%1000000009)*(a[i]%1000000009)%1000000009;
			}
		}else{
			for(int i=1;i<=k;i++) {
				ans=(ans%1000000009)*(a[i]%1000000009)%1000000009;
			}
		}
	}else if(cnt[2]>n-k){
		ans=0;
	}else if(cnt[2]>0&&cnt[2]==n-k&&cnt[1]&1){
		ans=0;
	}else{
		
		long long ne_cnt=0;
		int jc;
		for(int i=1;i<=k;i++) {
			if(a[i]<0){
				ne_cnt++;
			}
		}
		if(ne_cnt&1){
			long long aa[2],bb[2],cc[2],dd[2];
			bool f[4]={0,0,0,0};
			for(int i=k;i>=1;i--){
				if(a[i]<0){
					bb[0]=a[i];
					bb[1]=i;
					f[0]=1;
					break;
				}
			}
			for(int i=k+1;i<=n;i++){
				if(a[i]>0){
					aa[0]=a[i];
					aa[1]=i;
					f[1]=1;
					break;
				}
			}
			if(f[0]&&f[1]){
				jc=1;
			}
			for(int i=k;i>=1;i--){
				if(a[i]>0){
					dd[0]=a[i];
					dd[1]=i;
					f[2]=1;
					break;
				}
			}
			for(int i=k+1;i<=n;i++){
				if(a[i]<0){
					cc[0]=a[i];
					cc[1]=i;
					f[3]=1;
					break;
				}
			}
			if(f[2]&&f[3]){
				if(abs(cc[0])>abs(aa[0])){
					jc=2;
				}
			}
			if(jc==1){
				a[bb[1]]=aa[0];
			}else if(jc==2){
				a[dd[1]]=cc[0];
			}
			for(int i=1;i<=k;i++){
				ans=(ans%1000000009)*(a[i]%1000000009)%1000000009;
			}
		}else{
			for(int i=1;i<=k;i++){
				ans=(ans%1000000009)*(a[i]%1000000009)%1000000009;
			}
		}
	}
	cout<<ans;
	return 0;
}