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).

Examples

Input

4 2
1 2 -3 -4


Output

12


Input

4 3
-1 -2 -3 -4


Output

1000000001


Input

2 1
-1 1000000000


Output

1000000000


Input

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


Output

999983200
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * https://atcoder.jp/contests/abc173/submissions/15455890 を参考に実装したソースコード
 */
public class Main {

	private static final long MOD = 1_000_000_007L;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), k = scanner.nextInt();
			long[] a = IntStream.range(0, n).mapToLong(i -> scanner.nextLong()).sorted().toArray();
			int left = 0, right = n - 1;
			long answer = (1 == (k & 1)) ? a[right--] : 1L;
			long sign = (answer < 0) ? -1 : 1;
			while (k > 1) {
				if (sign * a[left] * a[left + 1] >= sign * a[right] * a[right - 1]) {
					answer = answer * a[left++] % MOD;
					answer = answer * a[left++] % MOD;
				} else {
					answer = answer * a[right--] % MOD;
					answer = answer * a[right--] % MOD;
				}
				k -= 2;
			}
			System.out.println((answer + MOD) % MOD);
		}
	}
}
