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 MOD=(int) (1e9+7);
	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();
   ArrayList<Long> al=new ArrayList<>();
    for(int i=0;i<n;i++){
		al.add(sc.nextLong());
      
    }
    ArrayList<Long> b=new ArrayList<>(al);

    List<Long> pos = new ArrayList<>();
    List<Long> neg = new ArrayList<>();
    int zero = 0;
    for (long i : al) {
      if (i > 0) {
        pos.add(i);
      } else if (i < 0) {
        neg.add(i);
      } else {
        zero++;
      }
    }

    Collections.sort(al);
   

    long ans=1; 
    if (pos.size() + neg.size() < k || (n == k && zero > 0)) {
        System.out.println(0);
        return;
      }
    if(k==n) {
    for(long i:al) {
    	ans=mul(ans,i);
    }
	 System.out.println(Math.floorMod(ans, MOD));
    
    }else {
    	 if (al.get(n-1) <= 0 && k % 2 != 0) { 
             for (int i = n - 1; i >= n - k; i--) 
               ans =mul(ans,al.get(i)); 
        	 System.out.println(Math.floorMod(ans, MOD));
         }else {
    
    
    	int i=0;int j=n-1;
    	if(k%2!=0) {
    		ans=mul(ans,al.get(j));
    		j--;
    		k--;
    	}
    	k=k>>1;
    	for( int itr =0;itr<k;itr++) {
    		long lf=Math.multiplyExact(al.get(i), al.get(i+1));
    		long rf=Math.multiplyExact(al.get(j), al.get(j-1));
    		if(lf>rf) {
    			ans=mul(ans,lf);
    			i=i+2;
    		}else {
    			ans=mul(ans,rf);
    			j=j-2;
    		}
    	}
    	System.out.println(ans%MOD);
    }
    }
    
	}
	  static long mul(long a, long b) {
		    return (((a + MOD) % MOD) * ((b + MOD) % MOD)) % MOD;
		  }
	}
	


  
   