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
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
       long long int n,k;
       cin>>n>>k;
       long long int a[n];
       for(long int i=0;i<n;i++)
       cin>>a[i];
       sort(a,a+n);
       long long int ans=1;
       long long int mod=1e9+7;
       if(a[n-1]==0 && (k&1))
       ans=0;
       else if(a[n-1]<0 && (k&1))
       {
           for(long int i=n-1;i>=n-k;i--)
           ans=(ans*a[i])%mod;
       }
       else
       {
           long int j=n-1;
           if(k&1)
           {
           ans=(ans*a[j])%mod;
           j--;
           }
           long int i=0;
           k>>=1;
           for(long int s=0;s<k;s++)
           {
               if(a[i]*a[i+1]>a[j]*a[j-1])
               {
                   long long int temp=(a[i]*a[i+1])%mod;
                   i+=2;
                   ans=(ans*temp)%mod;
               }
               else
               {
                   long long int temp=(a[j]*a[j-1])%mod;
                   j-=2;
                   ans=(ans*temp)%mod;
               }
           }
       }
       ans=(ans+mod)%mod;
       cout<<ans;
	// your code goes here
	return 0;
}
