40分，求大佬救命！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int mod=1000000009;
int a[N];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n,k,ans=1,f=1;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	if(k%2!=0){//如果k为奇数，则变成偶数，答案乘最大的 
		ans=ans*a[n]%mod;
		k-=1,n-=1;
		if(ans<0){
			f=-1;
		}
	}
	int l=1,r=n;
	while(k){//两边枚举 
		int p=a[l]*a[l+1]%mod;
		int q=a[r]*a[r-1]%mod;
		if(q*f>p*f){
			ans=q*ans%mod;
			l+=2;
		}
		else{
			ans=p*ans%mod;
			r-=2;
		}
		k-=2;
	}
	cout<<ans;
	return 0;
}