package zhenti;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;
public class zuida{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int beichushu = 1000000009;
ArrayList zhengArrayList = new ArrayList<>();
ArrayList fuArrayList = new ArrayList<>();
int zero = 0;
int temp = 0;
for (int i = 1; i <= n; i++) {
temp = scanner.nextInt();
if (temp > 0) {
zhengArrayList.add(temp);
}else if (temp < 0) {
fuArrayList.add(temp);
}else {
zero++;
}
}
scanner.close();
zhengArrayList.sort(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2 - o1;
}
});
fuArrayList.sort(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o1 - o2;
}
});
long ans = 1;
int zhenglength = zhengArrayList.size();
int fulength = fuArrayList.size();
if (zhenglength == n) {
for (int i = 1; i <= k; i++) {
ans = (zhengArrayList.get(i -1) * (long)ans) % beichushu;
}
}else if (fulength == n) {
if(k % 2 ==1) {
for (int i = 1; i <= k; i++) {
ans = (ans * fuArrayList.get(fulength - i)) % beichushu;
}
}else {
for (int i = 1; i <= k; i++) {
ans = (fuArrayList.get(i -1) * ans) % beichushu;
}
}
}else if(zero == n) {
ans = 0;
}else if(fulength == 0) {
if (k > zhenglength) {
ans = 0;
}else if(k <= zhenglength) {
for (int i = 1; i <= k; i++) {
ans = (zhengArrayList.get(i -1) * ans) % beichushu;
}
}
}else if(zhenglength == 0) {
if(k > fulength) {
ans = 0;
}else if(k <= fulength) {
if(k % 2 ==1) {
for (int i = 1; i <= k; i++) {
ans = (ans * fuArrayList.get(fulength - i)) % beichushu;
}
}else {
for (int i = 1; i <= k; i++) {
ans = (fuArrayList.get(i -1) * ans) % beichushu;
}
}
}
}else if(zero == 0) {
int muqianzheng = 0;
int muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= ((-1) * fuArrayList.get(muqianfu))) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
if (ans < 0 && k < (zhenglength + fulength)) {
if (muqianfu == fulength) {
ans = 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength - 1) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
//ans = ans / fuArrayList.get(muqianfu - 1) * zhengArrayList.get(muqianzheng);
}else if (muqianzheng == zhenglength) {
ans = 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength - 1) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= ((-1) * fuArrayList.get(muqianfu))) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
//ans = ans/ zhengArrayList.get(muqianzheng - 1) * fuArrayList.get(muqianfu);
}else {
int ans1 = Math.abs(fuArrayList.get(muqianfu) / zhengArrayList.get(muqianzheng - 1));
int ans2 = Math.abs(zhengArrayList.get(muqianzheng) / fuArrayList.get(muqianfu - 1));
if(ans1 > ans2) {
ans = 1;
int maxzheng = muqianzheng - 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == maxzheng) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
}else {
ans = 1;
int maxfu = muqianfu - 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == maxfu) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
}
}
}
}else {
if (k > zhenglength + fulength) {
ans = 0;
}else {
int muqianzheng = 0;
int muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
if (ans < 0 && k < (zhenglength + fulength)) {
if (muqianfu == fulength) {
ans = 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength - 1) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
//ans = ans / fuArrayList.get(muqianfu - 1) * zhengArrayList.get(muqianzheng);
}else if (muqianzheng == zhenglength) {
ans = 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength - 1) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
//ans = ans/ zhengArrayList.get(muqianzheng - 1) * fuArrayList.get(muqianfu);
}else {
int ans1 = Math.abs(fuArrayList.get(muqianfu) / zhengArrayList.get(muqianzheng - 1));
int ans2 = Math.abs(zhengArrayList.get(muqianzheng) / fuArrayList.get(muqianfu - 1));
if(ans1 > ans2) {
ans = 1;
int maxzheng = muqianzheng - 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == maxzheng) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == fulength) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
}else {
ans = 1;
int maxfu = muqianfu - 1;
muqianzheng = 0;
muqianfu = 0;
for (int i = 1; i <= k; i++) {
if (muqianzheng == zhenglength) {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}else if(muqianfu == maxfu) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else if (zhengArrayList.get(muqianzheng) >= (-1) * fuArrayList.get(muqianfu)) {
ans = (zhengArrayList.get(muqianzheng) * ans) % beichushu;
muqianzheng++;
}else {
ans = (fuArrayList.get(muqianfu) * ans) % beichushu;
muqianfu++;
}
}
}
}
}
}
}
System.out.println(ans);
}
}
