solution.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, k;
    long long ans;
    cin >> n >> k;
    vector<long long> num;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        num.push_back(temp);
    }
    sort(num.begin(), num.end());
    if (k % 2 != 0)
    {
        ans = num.back();
        k = k - 1;
        num.pop_back();
    }
    else
        ans = 1;
    while (k > 0)
    {
        if ((num[0] * num[1]) > num.at(num.size() - 1) * num.at(num.size() - 2))
        {
            ans = ans * num[0] * num[1] % 1000000009;
            num.erase(num.begin(), num.begin() + 1);
        }
        else
        {
            ans = ans * num.at(num.size() - 1) * num.at(num.size() - 2) % 1000000009;
            num.pop_back();
            num.pop_back();
        }
        k -= 2;
    }
    cout << ans;
    return 0;
}