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.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int k = sc.nextInt();
		Long[] list = new Long[n];
		boolean allminus = true;
		for(int i = 0; i < n; i++){
		    long a = sc.nextLong();
		    list[i] = a;
		    if(a > 0) allminus = false;
		}
		
		Arrays.sort(list, (s, t) -> {
		    if(abs(s) == abs(t)){
		        return Long.compare(s, t);
		    }
		    return Long.compare(abs(t), abs(s));
		});
		//System.out.println(Arrays.toString(list));
		
		// 計算
		long result = 1;
		int MOD = 1000000007;
		int signum = 1;
		for(int i = 0; i < k; i++){
		    signum *= Long.signum(list[i]);
		}
		if(signum >= 0){
		    for(int i = 0; i < k; i++){
		        result *= list[i];
		        result = (result%MOD + MOD)%MOD;
		    }
		    //System.out.println("A");
		}else if(allminus){
		    for(int i = n-1; i > n-1-k; i--){
		        result *= list[i];
		        result = (result%MOD + MOD)%MOD;
		    }
		    //System.out.println("B");
		}else{
		    int indexM = -1;
		    for(int i = k-1; i >= 0; i--){
		        if(list[i] < 0){
		            indexM = i;
		            break;
		        }
		    }
		    int indexP = -1;
		    for(int i = k-1; i >= 0; i--){
		        if(list[i] >= 0){
		            indexP = i;
		            break;
		        }
		    }
		    long tmpA = -1;
		    int indexA = -1;
		    for(int i = k; i < n; i++){
		        if(indexM < 0) break;
		        if(list[i] >= 0){
		            tmpA = 0;
		            if(indexP >= 0) tmpA = list[indexP]*list[i];
		            indexA = i;
		            break;
		        }
		    }
		    long tmpB = -1;
		    int indexB = -1;
		    for(int i = k; i < n; i++){
		        if(indexP < 0) break;
		        if(list[i] < 0){
		            tmpB = 0;
		            if(indexM >= 0) tmpB = list[indexM]*list[i];
		            indexB = i;
		            break;
		        }
		    }
		    if(tmpA > tmpB && indexM >= 0 && indexA >= 0){
		        for(int i = 0; i < k; i++){
		            if(i == indexM) continue; 
		            result *= list[i];
		            result = (result%MOD + MOD)%MOD;
		        }
		        result *= list[indexA];
		        result = (result%MOD + MOD)%MOD;
		        //System.out.println("C");
		    }else if(indexP >= 0 && indexB >= 0){
		        for(int i = 0; i < k; i++){
		            if(i == indexP) continue; 
		            result *= list[i];
		            result = (result%MOD + MOD)%MOD;
		        }
		        result *= list[indexB];
		        result = (result%MOD + MOD)%MOD;
		        //System.out.println("D");
		    }else{
		        for(int i = 0; i < k; i++){
		            result *= list[i];
		            result = (result%MOD + MOD)%MOD;
		        }
		        //System.out.println("E");
		    }
		}
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}

