[//]: # python
python
n,k=map(int,input().split())
a=[] # 列表a的值是一行行输入
for i in range(n):
a.append(int(input()))
# 对列表进行排序
a.sort()
res,sign=1,1
l,r=0,n-1 # 左端点与右端点
mod=1000000009
# 对k为奇数特判,将其减一,k-1就为偶数,代入同样的循环即可
if k%2==1:
res=a[-1]
r-=1 # res取了最右边的值,所以r需要减一
k-=1 # 这样所有的k都为偶数
# 判断一下是不是所有的a[]都是负数
if res<0:
sign=-1 # sign=-1 代表着k是奇数,且所有的数都是负数,所以k个数的乘积也一定是负数
while k:
x,y=a[l]*a[l+1],a[r-1]*a[r]
# 如果左边两个数的乘积大于有右边两个数的乘积,先判断最终乘积是不是负数,再将l+2
if x*sign>=y*sign:
if x*sign<0:
res=-(abs(x*res)%mod)
else:
res=x*res%mod
l+=2
# 如果右边两个数的乘积大于左边两个数的乘积,先判断最终乘积是不是负数,再将r-2
else:
if y*sign<0:
res=-(abs(y*res)%mod)
else:
res=y*res%mod
r-=2
k-=2 # 一次性取两个值,k减二
print(res)