AT_abc173_e.[ABC173E] Multiplication 4

给定 $N$ 个整数 $A_1,\ldots,A_N$。

请从中恰好选择 $K$ 个元素，求所能得到的元素乘积的最大值。

然后，将答案对 $10^9+7$ 取模，输出一个在 $0$ 到 $10^9+6$ 之间的整数。

输入以如下格式从标准输入给出。

$N$ $K$ $A_1$ $ \ldots $ $A_N$

请输出将答案对 $10^9+7$ 取模后的结果，输出一个在 $0$ 到 $10^9+6$ 之间的整数。

限制条件

• $1 \leq K \leq N \leq 2\times 10^5$
• $|A_i| \leq 10^9$

样例解释 1

当选择 $2$ 个元素时，可能的乘积有 $2,-3,-4,-6,-8,12$，因此最大值为 $12$。

样例解释 2

当选择 $3$ 个元素时，可能的乘积有 $-24,-12,-8,-6$，因此最大值为 $-6$。将其对 $10^9+7$ 取模，输出 $1000000001$。

样例解释 3

当选择 $1$ 个元素时，可能的乘积有 $-1,1000000000$，因此最大值为 $1000000000$。

样例解释 4

请输出将答案对 $10^9+7$ 取模后的结果。

由 ChatGPT 4.1 翻译