# 乘积最大

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)
#### 输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

#### 输出格式

输出一个整数，表示答案。

#### 数据范围

```
1≤K≤N≤105,
−105≤Ai≤105
```
#### 输入样例1：

```
5 3
-100000
-10000
2
100000
10000
```
#### 输出样例1：

```
999100009
```
#### 输入样例2：

```
5 3
-100000
-100000
-2
-100000
-100000
#### 输出样例2：

-999999829
```

## aop

### before

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
```
### after

```cpp

```

## 答案

```cpp
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;
}

```
## 选项


### A

```cpp
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()) * num.at(num.size() - 1))
        {
            ans = ans * num[0] * num[1] % 1000000009;
            num.erase(num.begin(), num.begin() + 1);
        }
        else
        {
            ans = ans * num.at(num.size()) * num.at(num.size() - 1) % 1000000009;
            num.pop_back();
            num.pop_back();
        }
        k -= 2;
    }
    cout << ans;
    return 0;
}
```

### B

```cpp
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() - 1))
        {
            ans = ans * num[0] * num[1] % 1000000009;
            num.erase(num.begin(), num.begin() + 1);
        }
        else
        {
            ans = ans * num.at(num.size() - 1) % 1000000009;
            num.pop_back();
            num.pop_back();
        }
        k -= 2;
    }
    cout << ans;
    return 0;
}
```

### C

```cpp
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) % 1000000009;
            num.pop_back();
            num.pop_back();
        }
        k -= 2;
    }
    cout << ans;
    return 0;
}
```