分数: 500 点
问题陈述
给出的是 N 整数 A_1,\ldots,A_N.
我们会准确选择 K 这些元素。找出所选元素的最大可能乘积。
然后,打印最大乘积模 (10^9+7),使用之间的整数 0 和 10^9+6 (含)。
约束
- 1 \leq K \leq N \leq 2\times 10^5
- |A_i| \leq 10^9
输入
输入由标准输入按以下格式给出:
N K A_1 \ldots A_N
输出
打印最大乘积模数 (10^9+7),使用之间的整数 0 和 10^9+6 (含)。
示例输入 1
4 2 1 2 -3 -4
示例输出 1
12
两个所选元素的可能乘积是 2, -3, -4, -6, -8,和 12,所以最大乘积为 12.
示例输入 2
4 3 -1 -2 -3 -4
示例输出 2
1000000001
三个选定元素的可能乘积是 -24, -12, -8,和 -6,所以最大乘积为 -6.
我们打印这个值模 (10^9+7),即 1000000001.
示例输入 3
2 1 -1 1000000000
示例输出 3
1000000000
一种所选元素的可能产物是 -1 和 1000000000,所以最大乘积为 1000000000.
示例输入 4
10 10 1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
示例输出 4
999983200
请务必打印乘积模数 (10^9+7).