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

输入 #1

4 2
1 2 -3 -4

输出 #1

12

输入输出样例 #2

输入 #2

4 3
-1 -2 -3 -4

输出 #2

1000000001

输入输出样例 #3

输入 #3

2 1
-1 1000000000

输出 #3

1000000000

输入输出样例 #4

输入 #4

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

输出 #4

999983200

说明/提示

限制条件

• $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 翻译