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.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int MOD = 1_000_000_007;
		int N = sc.nextInt();
		int K = sc.nextInt();
		long[] A = new long[N];
		int neg = 0, zero = 0, plus = 0;
		long ans = 1;
		for(int i = 0; i < N; i++) {
			A[i] = sc.nextLong();
			if(A[i] > 0)
				plus++;
			else if(A[i] == 0)
				zero++;
			else
				neg++;
		}
		if((neg / 2 * 2) + plus >= K && (plus != 0 || K % 2 == 0)) {
			// ans > 0
			Arrays.sort(A);	
			List<Long> l = new ArrayList<>();
			for(int i = 1; i < N; i+=2) {
				if(A[i] >= 0)
					break;
				l.add(A[i] * A[i-1]);
			}
			if(K % 2 == 1) {
				ans = A[N-1];
				K--;
				N--;
			}
			for(int i = N-2; i >= 0; i-=2) {
				if(A[i] <= 0)
					break;
				l.add(A[i] * A[i+1]);
			}
			Collections.sort(l, Collections.reverseOrder());
			for(int i = 0; i < K / 2; i++)
				ans = ans * (l.get(i) % MOD) % MOD;
			System.out.println(ans);
		}
		else {
			// ans <= 0
			if(zero > 0) {
				System.out.println(0);
				return;
			}
			// ans < 0
			long[] abs = new long[N];
			for(int i = 0; i < N; i++)
				abs[i] = Math.abs(A[i]);
			Arrays.sort(abs);
			ans = -1;
			for(int i = 0; i < K; i++)
				ans = ans * abs[i] % MOD;
			System.out.println((ans + MOD) % MOD);
		}
	}

}