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.*;
import java.util.*;

class Main
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        String s[]=bu.readLine().split(" ");
        int n=Integer.parseInt(s[0]),k=Integer.parseInt(s[1]);
        s=bu.readLine().split(" ");
        int i,a[]=new int[n];
        for(i=0;i<n;i++)
        a[i]=Integer.parseInt(s[i]);
        Arrays.sort(a);
        long ans=1,M=1000000007;
        ans=maxProduct(a,n,k);
        ans=(ans+M)%M;
        System.out.print(ans);
    }

    static long maxProduct(int A[], int n, int k)
    {
        long product=1,M=1000000007;

        if(A[n-1]==0 && k%2!=0)  return 0;
        if(A[n-1]<=0 && k%2!=0)
        {
            for(int i=n-1; i>=n-k;i--) product=(product*A[i])%M;
            return product;
        }

        int i=0,j=n-1;
        if(k%2!=0)
        {
            product=product*A[j]%M;
            j--;
            k--;
        }
        k>>=1;

        for(int itr=0;itr<k; itr++)
        {
            long left_product=1l*A[i]*A[i+1];
            long right_product=1l*A[j]*A[j-1];

            if(left_product>right_product)
            {
                product=product*(left_product%M)%M;
                product%=M;
                i+=2;
            }
            else
            {
                product=product*(right_product%M)%M;
                product%=M;
                j-=2;
            }
        }
        return product;
    }
}