#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[320948],ans=1,le,ri;
int mod=1000000009;
signed main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	if(k%2==1)
	{
		ans*=a[n-1];
		n--;
		k--;
	}
	le=0;
	ri=n-1;
	while(k)
	{
		if(a[le]*a[le+1]>a[ri]*a[ri-1])
		{
			ans=ans%mod*a[le]%mod*a[le+1]%mod;
			le+=2;
		}
		else
		{
			ans=ans%mod*a[ri]%mod*a[ri-1]%mod;
			ri-=2;
		}
		k-=2;
	}
	cout<<ans<<endl;
	return 0;
}