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) throws Exception {
		Scanner sc=new Scanner(System.in);

		int n=sc.nextInt();
		int k=sc.nextInt();

		long[] a= new long[n];

		int mod=(int)Math.pow(10,9)+7;

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

		Arrays.sort(a);
		
		int left=0;
		int right=n-1;
		
		long ans= k%2==0? 1:a[right--];
		int c=1;
		if(ans<0)c=-1;
		
		while(k>=2) {
			if(c*a[left]*a[left+1]>c*a[right]*a[right-1]) {
				ans=ans*a[left]%mod;
				ans=ans*a[left+1]%mod;
				left+=2;
			}else {
				ans=ans*a[right]%mod;
				ans=ans*a[right-1]%mod;
				right-=2;
			}
			k-=2;
		}
		



		if(ans<0)ans+=mod;
		System.out.println(ans);

	}
}