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$（含）之间的整数。

4 2
1 2 -3 -4

12

4 3
-1 -2 -3 -4

1000000001

2 1
-1 1000000000

1000000000

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

999983200

提示

$1 \leq K \leq N \leq 2\times 10^5$ $|A_i| \leq 10^9$两个被选中元素的可能乘积为 $2$, $-3$, $-4$, $-6$, $-8$ 和 $12$，因此最大乘积是 $12$。
三个被选中元素的可能乘积为 $-24$, $-12$, $-8$ 和 $-6$，因此最大乘积是 $-6$。 我们将该值对 $(10^9+7)$ 取模，即 $1000000001$。
一个被选中元素的可能乘积为 $-1$ 和 $1000000000$，因此最大乘积是 $1000000000$。
请确保输出乘积对 $(10^9+7)$ 的模。

标签: AtCoder|abc173E

来源

AtCoder|abc173E