#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;
typedef long long LL;

const int N = 1e5 + 5, mod = 1e9 + 9;
const double INF = 1e10;

int n, k, a[N];

bool cmp(int a, int b)
{
    return abs(a) > abs(b);
}

LL get_min()
{
    LL ans = 1;
    for (int i = n; i >= n - k + 1; i--)
    {
        ans *= a[i];
        if (ans < 0)
            ans = 0 - ((-ans) % mod);
        else
            ans %= mod;
    }
    return ans;
}

LL get_max(int b, int tar)
{
    LL ans = 1;
    for(int i = 1; i <= k; i++)
    {
        if(i != b)
        {
            ans *= a[i];
            if(ans < 0) 
                ans = 0 - (-ans) % mod;
            else
                ans %= mod;
        }
    }
    if(b != -1)
        ans = ans * a[tar] % mod;
    return ans;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1, cmp);
    int cnt = 0, p1 = -1, p2 = -1, m1 = -1, m2 = -1;
    LL ans = 1;
    for (int i = 1; i <= k; i++)
        if (a[i] < 0)
            cnt++;
    if (cnt & 1) // 绝对值最大的k个数字只能得到负数
    {
        for (int i = k; i; i--)
        {
            if (p1 != -1 && m1 != -1)
                break;
            if (p1 != -1 && a[i] > 0)
                p1 = i;
            if (m1 != -1 && a[i] < 0)
                m1 = i;
        }
        for (int i = k + 1; i <= n; i++)
        {
            if (p2 != -1 && m2 != -1)
                break;
            if (p2 != -1 && a[i] > 0)
                p2 = i;
            if (m2 != -1 && a[i] < 0)
                m2 = i;
        }
        bool f1 = true, f2 = true;
        if(m1 != -1 && p2 != -1)
        {
            f1 = false;
            ans = get_max(m1, p2);
        }
        if(p1 != -1 && m2 != -1)
        {
            f2 = false;
            ans = max(ans, get_max(p1, m2));
        }
        if (f1 && f2) // 无法得到正数
        {
            ans = get_min();
        }
    }
    else
        ans = get_max(-1, -1);
    printf("%lld\n", ans);
    return 0;
}