E - Multiplication 4 /

Time Limit: 2 sec / Memory Limit: 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).