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 {
	static int r = 1000000000 + 7;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt();
		int a[] = new int[n];
		for (int i = 0; i < n; ++i)
			a[i] = sc.nextInt();
		sc.close();
		Arrays.sort(a);
		long ans = 1;
		if(a[0] >= 0){
			for (int i = 0; i < k; ++i) {
				ans *= (long) a[n - i - 1];
				ans %= r;
			}	
		}
		else if(a[n - 1] <= 0){
			if(k % 2 == 1){
				for (int i = 0; i < k; ++i) {
					ans *= (long) a[n - i - 1];
					ans %= r;
				}	
			}else{
				for (int i = 0; i < k; ++i) {
					ans *= (long) a[i];
					ans %= r;
				}	
			}
		}
		else {
			long minus = 1, plus = 1;
			int curl = 0, curr = n - 1;
			if(k % 2 == 1){
				ans *= (long)a[n - 1];
				ans %= r;
				--k;
				--curr;
			}
			for (int i = 2; i <= k; i += 2) {
				minus = (long)a[curl] * (long)a[curl + 1];
				plus = (long)a[curr] * (long)a[curr - 1];
				if(minus >= plus){
					minus %= r;
					ans *= minus;
					ans %= r;
					curl += 2;
				}
				else{
					plus %= r;
					ans *= plus;
					ans %= r;
					curr -= 2;
				}
			}
		}
		if (ans < 0) {
			ans += r;
		}
		System.out.println(ans);
	}
}
