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 final int MOD = (int)1e9+7;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        long[] a = new long[n];
        for(int i=0; i<n; i++){
            a[i] = Long.parseLong(sc.next());
        }
        Arrays.sort(a);
        long ans = 1;
        if(a[n-1]<=0){
            if(k%2==1){
                for(int i=0; i<k-1; i+=2){
                    long tmp = a[n-1-i]*a[n-2-i]%MOD;
                    ans = ans*tmp%MOD;
                }
                ans = ans*a[n-k]%MOD;
            }else{
                for(int i=0; i<k; i+=2){
                    long tmp = a[i]*a[i+1]%MOD;
                    ans = ans*tmp%MOD;
                }
            }
        }else{
            int l = 0;
            int r = n-1;
            if(k%2==1){
                ans = ans*a[r]%MOD;
                r--;
            }
            while(k>1){
                long m = a[l]*a[l+1];
                long p = a[r]*a[r-1];
                if(m >= p){
                    ans = ans*(m%MOD)%MOD;
                    l+=2;
                }else{
                    ans = ans*(p%MOD)%MOD;
                    r-=2;
                }
                k-=2;
            }
        }
        System.out.println((ans+MOD)%MOD);
    }
}
