/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 個選んだときの積としてありえる値は 2,-3,-4,-6,-8,12 なので、最大値は 12 です。
入力例 2
4 3 -1 -2 -3 -4
出力例 2
1000000001
要素を 3 個選んだときの積としてありえる値は -24,-12,-8,-6 なので、最大値は -6 です。
これを (10^9+7) で割った余りである 1000000001 を出力します。
入力例 3
2 1 -1 1000000000
出力例 3
1000000000
要素を 1 個選んだときの積としてありえる値は -1,1000000000 なので、最大値は 1000000000 です。
入力例 4
10 10 1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
出力例 4
999983200
答えを (10^9+7) で割った余りを出力してください。
Score : 500 points
Problem Statement
Given are N integers A_1,\ldots,A_N.
We will choose exactly K of these elements. Find the maximum possible product of the chosen elements.
Then, print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).
Constraints
- 1 \leq K \leq N \leq 2\times 10^5
- |A_i| \leq 10^9
Input
Input is given from Standard Input in the following format:
N K A_1 \ldots A_N
Output
Print the maximum product modulo (10^9+7), using an integer between 0 and 10^9+6 (inclusive).
Sample Input 1
4 2 1 2 -3 -4
Sample Output 1
12
The possible products of the two chosen elements are 2, -3, -4, -6, -8, and 12, so the maximum product is 12.
Sample Input 2
4 3 -1 -2 -3 -4
Sample Output 2
1000000001
The possible products of the three chosen elements are -24, -12, -8, and -6, so the maximum product is -6.
We print this value modulo (10^9+7), that is, 1000000001.
Sample Input 3
2 1 -1 1000000000
Sample Output 3
1000000000
The possible products of the one chosen element are -1 and 1000000000, so the maximum product is 1000000000.
Sample Input 4
10 10 1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
Sample Output 4
999983200
Be sure to print the product modulo (10^9+7).