← 返回题目列表

AtCoder · abc173_e

E. 乘法 4

中文机器翻译题面 查看原题

分数: 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).