乘积最大

给你两个数 N、K，从 N 个数中选出 K 个使得乘积最大。输出乘积在数学意义上对 10⁹+7 取模的值。

时间限制：1000ms，内存限制：256MB

输入格式

第一行：两个整数 N、K；

第二行：N 个整数 a₁、a₂、……、a_n。

输出格式

一个整数表示答案。

输入样例#1

4 2
1 2 -3 -4

输出样例#1

12

输入样例#2

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

输出样例#2

999983200

数据范围：

1≤K≤N≤2×10⁵，-10⁹≤a_i≤10⁹。

本题需要使用动态规划来解决，具体实现细节需要根据题目要求进行调整和优化。大致思路如下：

1. 创建一个数组dp，其中dp[i][j]表示从前i个数中选择j个数的最大乘积。初始化时，将所有元素初始化为一个较小的值，例如负无穷大。
2. 对于数组中的每个元素，考虑两种情况：包含该元素和不包含该元素。如果包含该元素，则需要从前面的i-1个数中选择j-1个数，使得乘积最大；如果不包含该元素，则需要从前面的i-1个数中选择j个数。因此，状态转移方程为：dp[i][j] = max(dp[i-1][j], a[i] * dp[i-1][j-1])。其中a[i]表示当前元素的值。
3. 由于数据范围较大，需要对乘积进行取模操作，避免溢出。在每次计算乘积后，使用取模运算对结果取模，保证结果在指定范围内。
4. 最终答案为dp[N][K]。由于数据范围较大，需要使用高精度算法来处理大数取模运算。可以使用快速幂取模算法或其他高效的大数取模算法来实现。

该题是一个典型的动态规划问题，通过状态转移方程来求解最大乘积。在实现过程中需要注意数据范围的限制和取模运算的处理。由于数据范围较大，需要使用高精度算法来保证结果的正确性。具体实现细节需要根据题目要求进行调整和优化。