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.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Vector;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int mod = 1_000_000_007;

		Integer a[] = new Integer[n];
		Vector<Integer> posZero = new Vector<Integer>();
		Vector<Integer> neg = new Vector<Integer>();

		for(int i = 0; i < n; i++){
			a[i] = sc.nextInt();

			if(a[i] < 0){
				neg.add(a[i]);
			}
			else{
				posZero.add(a[i]);
			}
		}

		if(n == k){
			long result = 1;

			for(int i = 0; i < n; i++){
				if(a[i] >= 0){
					result = result * a[i] % mod;
				}
				else {
					result = result * (a[i] + mod)%mod;
				}
			}

			System.out.println(result);
			return;
		}



		Collections.sort(posZero, new Comparator<Integer>() {

			@Override
			public int compare(Integer n1, Integer n2) {
				// TODO 自動生成されたメソッド・スタブ
				return Math.abs(n2) - Math.abs(n1);
			}
		});

		Collections.sort(neg, new Comparator<Integer>() {

			@Override
			public int compare(Integer n1, Integer n2) {
				// TODO 自動生成されたメソッド・スタブ
				return Math.abs(n2) - Math.abs(n1);
			}
		});

		if(neg.size() == n && k%2 == 1){
			long result = 1;
			for(int i = 0; i < k; i++){
				result = result * (neg.get(n - i - 1) + mod)%mod;
			}

			System.out.println(result);
			return;
		}

		long result = 1;
		int posIndex = 0;
		int negIndex = 0;
		for(int i = 0; i < k; i++){
			if(i == k - 1 || negIndex >= neg.size() - 1){
				result = result*posZero.get(posIndex)%mod;
				posIndex++;
			}
			else if(posIndex >= posZero.size() - 1){
				result = result*(neg.get(negIndex) + mod)%mod*(neg.get(negIndex + 1) + mod)%mod;
				negIndex += 2;
				i++;
			}
			else {
				long tmp1 = (long)posZero.get(posIndex)*posZero.get(posIndex + 1);
				long tmp2 = (long)neg.get(negIndex)*neg.get(negIndex + 1);

//				System.out.println(tmp1 + " " +tmp2);
				if(tmp1 > tmp2){
					result = result*posZero.get(posIndex)%mod;
					posIndex++;
				}
				else {
					result = result*(neg.get(negIndex) + mod)%mod*(neg.get(negIndex + 1) + mod)%mod;
					negIndex += 2;
					i++;
				}
			}

//			System.out.println("i = "+i+" pos "+posIndex+"  neg "+negIndex+" / "+neg.size());
//			System.out.println(result);
		}

		System.out.println(result);
	}

}
