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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
	
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastInput in = new FastInput(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		ABC173E solver = new ABC173E();
		solver.solve(1, in, out);
		out.close();
	}

	static class ABC173E {

		static int mod = 1000000007;
		public void solve(int testNum, FastInput in, PrintWriter out) {
			
			int n = in.nextInt();
			int k = in.nextInt();
			
			int []a = in.nextIntArray(n);
			
			long ans = 1L;
			
			if(n == k) {
				for(int i = 0 ; i < n ;i++) {
					int p = a[i];
					if(a[i] < 0) {
						p = mod + p;
					}
					ans = (long)(ans * p)%mod;
				}
				out.println(ans);
				return ;
			}
			
			List<Integer>P = new ArrayList<Integer>();
			List<Integer>N = new ArrayList<Integer>();
			
			for(int i = 0 ; i < n ;i++) {
				if(a[i] > 0) {
					P.add(a[i]);
				}
				else {
					N.add(a[i]);					
				}
			}
			
			if(k % 2 == 1 && P.isEmpty()) {
				Collections.sort(N,Comparator.reverseOrder());
				for(int i = 0; i < k ;i++) {
					ans = (long)((ans *(mod + N.get(i)))%mod);
				}
				out.println(ans);
				return;
			}
			
			Collections.sort(P,Comparator.reverseOrder());
			Collections.sort(N);
			
			if(k % 2 == 1) {
				ans *= P.get(0);
				P.remove(0);
				k--;
			}
			
			int cnt = 0;
			while(cnt < k) {
				
				if(P.size() <= 1) {
					long nn =(long)N.get(0)*N.get(1)%mod;
					ans = (long)(ans *nn)%mod;
					
					N.remove(0);
					N.remove(0);
				}
				else if (N.size() <= 1) {
					
					long pp = (long) P.get(0)*P.get(1)%mod;
					ans = (long)(ans*pp)%mod;
					P.remove(0);
					P.remove(0);
				}
				else {
					long nn =(long)N.get(0)*N.get(1);
					long pp =(long)P.get(0)*P.get(1);
					
					if(pp > nn) {
						ans = (long)ans*(pp%mod)%mod;
						P.remove(0);
						P.remove(0);
					}
					else {
						ans = (long)ans*(nn%mod)%mod;
						N.remove(0);
						N.remove(0);
						
					}
				}
				cnt += 2;
			}
			
			out.println(ans);
				
		}
			
		}
			
	
	static class FastInput{
	private final BufferedReader in;
	private String[] buff;
	private int index = 0;
	
	public FastInput(InputStream im) {
		in = new BufferedReader(new InputStreamReader(im));
	}
	String nextLine() {
		try {
			return in.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return null;
	}
	String next() {
		while (buff == null || index >= buff.length) {
			buff = nextLine().split(" ");
			index = 0;
		}
		return buff[index++];
	}
	int nextInt() {
		return Integer.parseInt(next());
	}
	
	long nextLong() {
		return Long.parseLong(next());
	}
	
	Double nextDouble() {
		return Double.parseDouble(next());
	}
	
	BigInteger nextBigInteger() {
		return new BigInteger(next());
	}
	
	BigDecimal nextBigDecimal() {
		return new BigDecimal(next());
	}
	
	public int[] nextIntArray(final int n) {
		final int[] res = new int [n];
		
		for(int i = 0 ; i < n ;i++) {
			res[i] = nextInt();
		}
		return res;
	}
	
	public long[] nextLongArray(final int n) {
		final long[] res= new long [n];
		
		for(int i = 0 ; i < n ;i++) {
			res[i] = nextLong();
		}
		return res;
	}
	
	public double[] nextDoubleArray(final int n ) {
		final double[] res = new double [n];
		
		for(int i = 0 ; i < n ;i++) {
			res[i] = nextDouble();
		}
		return res;
	}
	
	
	public int[][] nextInt2DArray(final int n , final int m){
		int [][]res = new int [n][m];
		
		for(int i = 0 ; i < n ;i++) {
			for(int j = 0 ; j < m ;j++) {
				res[i][j] = nextInt();
			}
		}
		return res;
	}
	public long[][] nextLong2DArray(final int n , final int m){
		long [][]res = new long [n][m];
		
		for(int i = 0 ; i < n ;i++) {
			for(int j = 0 ; j < m ;j++) {
				res[i][j] = nextLong();
			}
		}
		return res;
	}
	
	public char[][] nextChar2DArray(final int n){
		char [][]res = new char [n][];
		
		for(int i = 0 ; i < n ;i++) {
			String s = next();
			res[i] = s.toCharArray();
		}
		
		return res;
	}
}



}
