#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;
#define all(c) (c).begin(),(c).end()
#define endl "\n"
#define ff first
#define ss second
#define allr(c) (c).rbegin(),(c).rend()
#define ifr(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define pof pop_front
#define pob pop_back
#define pb emplace_back
#define pf emplace_front
#define fstm(m,n,r) m.reserve(n);m.max_load_factor(r)
#define mp make_pair
#define mt make_tuple
#define inf LLONG_MAX
#define os tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
const double PI = acos(-1);
typedef complex<double> cd;
typedef long long ll;
ll gcd(){return 0ll;} template<typename T,typename... Args> T gcd(T a,Args... args) { return __gcd(a,(__typeof(a))gcd(args...)); }
typedef map<ll,ll> mll;
typedef map<string,ll> msll;
typedef unordered_map<ll,ll> umap;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mod 1000000007
#define N 100001
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
// int T;cin>>T;while(T--)
{
ll n, k, t;
cin>>n>>k;
vll pos, neg; ll zero = 0;
ifr(i, 0, n) {
cin>>t;
if(t==0) zero++;
else if(t<0) neg.pb(t);
else pos.pb(t);
}
ll ps = pos.size(), ns = neg.size();
if(k > (ps + ns)) {
cout<<"0\n";
return 0;
}
ll ans = 1;
if( k == (ps + ns)) {
// if((ns&1) && zero>0) {
// cout<<"0\n";
// return 0;
// }
ifr(i, 0, ps) ans = (ans*pos[i])%mod;
ifr(i, 0, ns) ans = (ans*neg[i])%mod;
ans = (ans + mod)%mod;
cout<<ans<<endl;
return 0;
}
sort(all(pos), greater<ll>());
sort(all(neg));
if(ns == 0) {
ans = 1;
ifr(i, 0, k) ans = (ans*pos[i])%mod;
cout<<ans<<endl;
return 0;
}
if(ps == 0) {
if(k&1) reverse(all(neg));
if((k&1) && zero>0) {
cout<<"0\n";
return 0;
}
ans = 1;
ifr(i, 0, k) ans = (ans*neg[i])%mod;
ans = (ans + mod)%mod;
cout<<ans<<endl;
return 0;
}
vector<ld> pre;
pre.pb(0);
ifr(i, 0, ps) pre.pb(pre.back() + log(pos[i]));
ld lg = 0, sum, msum = 0;
int x=-1, y=-1;
for(int i=0; i<=ns; i++) {
if(k-i<0 ) break;
if(((k-i)>ps) || (i&1)) {
lg += log(-neg[i]);
continue;
}
sum = lg + pre[k-i];
// cout<<sum<<" "<<msum<<endl;
if(msum < sum) {
msum = sum;
x = i; y = k-i;
}
if(i!=ns) lg += log(-neg[i]);
}
// cout<<x<<" "<<y<<endl;
if(x==-1) {
cout<<0<<endl;
return 0;
}
ans = 1;
if((x&1) && zero>0 ) {
cout<<"0\n";
return 0;
}
ifr(i, 0, x) ans = (1ll*ans*neg[i])%mod;
ifr(i, 0, y) ans = (1ll*ans*pos[i])%mod;
ans = (ans + mod)%mod;
cout<<ans<<endl;
}
return 0;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCItTzMiKQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KLy8gI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgovLyAjaW5jbHVkZSA8ZXh0L3BiX2RzL3RyZWVfcG9saWN5LmhwcD4KLy8gdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7Ci8vI2luY2x1ZGUgPGJvb3N0L211bHRpcHJlY2lzaW9uL2NwcF9pbnQuaHBwPgovL3VzaW5nIG5hbWVzcGFjZSBib29zdDo6bXVsdGlwcmVjaXNpb247CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGFsbChjKSAoYykuYmVnaW4oKSwoYykuZW5kKCkKI2RlZmluZSBlbmRsICJcbiIKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojZGVmaW5lIGFsbHIoYykgKGMpLnJiZWdpbigpLChjKS5yZW5kKCkKI2RlZmluZSBpZnIoaSwgYmVnaW4sIGVuZCkgZm9yIChfX3R5cGVvZihlbmQpIGkgPSAoYmVnaW4pIC0gKChiZWdpbikgPiAoZW5kKSk7IGkgIT0gKGVuZCkgLSAoKGJlZ2luKSA+IChlbmQpKTsgaSArPSAxIC0gMiAqICgoYmVnaW4pID4gKGVuZCkpKQojZGVmaW5lIHBvZiBwb3BfZnJvbnQKI2RlZmluZSBwb2IgcG9wX2JhY2sKI2RlZmluZSBwYiBlbXBsYWNlX2JhY2sKI2RlZmluZSBwZiBlbXBsYWNlX2Zyb250CiNkZWZpbmUgZnN0bShtLG4scikgbS5yZXNlcnZlKG4pO20ubWF4X2xvYWRfZmFjdG9yKHIpCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgbXQgbWFrZV90dXBsZQojZGVmaW5lIGluZiBMTE9OR19NQVgKI2RlZmluZSBvcyB0cmVlPGludCwgbnVsbF90eXBlLGxlc3M8aW50PiwgcmJfdHJlZV90YWcsdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPgovL29yZGVyX29mX2tleSAoaykgOiBOdW1iZXIgb2YgaXRlbXMgc3RyaWN0bHkgc21hbGxlciB0aGFuIGsgLgovL2ZpbmRfYnlfb3JkZXIoaykgOiBLLXRoIGVsZW1lbnQgaW4gYSBzZXQgKGNvdW50aW5nIGZyb20gemVybykuCmNvbnN0IGRvdWJsZSBQSSA9IGFjb3MoLTEpOwp0eXBlZGVmIGNvbXBsZXg8ZG91YmxlPiBjZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CmxsIGdjZCgpe3JldHVybiAwbGw7fSB0ZW1wbGF0ZTx0eXBlbmFtZSBULHR5cGVuYW1lLi4uIEFyZ3M+IFQgZ2NkKFQgYSxBcmdzLi4uIGFyZ3MpIHsgcmV0dXJuIF9fZ2NkKGEsKF9fdHlwZW9mKGEpKWdjZChhcmdzLi4uKSk7IH0KdHlwZWRlZiBtYXA8bGwsbGw+IG1sbDsKdHlwZWRlZiBtYXA8c3RyaW5nLGxsPiBtc2xsOwp0eXBlZGVmIHVub3JkZXJlZF9tYXA8bGwsbGw+IHVtYXA7CnR5cGVkZWYgdmVjdG9yPGxsPiB2bGw7CnR5cGVkZWYgcGFpcjxsbCxsbD4gcGxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwojZGVmaW5lIG1vZCAxMDAwMDAwMDA3IAojZGVmaW5lIE4gMTAwMDAxCgppbnQgbWFpbigpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKICAgIGNvdXQudGllKE5VTEwpOwogICAgI2lmbmRlZiBPTkxJTkVfSlVER0UKICAgICAgICBmcmVvcGVuKCJpbnB1dC50eHQiLCJyIixzdGRpbik7CiAgICAjZW5kaWYKICAgIC8vIGludCBUO2Npbj4+VDt3aGlsZShULS0pIAogICAgewogICAgICAgIGxsIG4sIGssIHQ7CiAgICAgICAgY2luPj5uPj5rOwogICAgICAgIHZsbCBwb3MsIG5lZzsgbGwgemVybyA9IDA7CiAgICAgICAgaWZyKGksIDAsIG4pICB7CiAgICAgICAgICAgIGNpbj4+dDsKICAgICAgICAgICAgaWYodD09MCkgemVybysrOwogICAgICAgICAgICBlbHNlIGlmKHQ8MCkgbmVnLnBiKHQpOwogICAgICAgICAgICBlbHNlIHBvcy5wYih0KTsKICAgICAgICB9CiAgICAgICAgbGwgcHMgPSBwb3Muc2l6ZSgpLCBucyA9IG5lZy5zaXplKCk7CiAgICAgICAgaWYoayA+IChwcyArIG5zKSkgewogICAgICAgICAgICBjb3V0PDwiMFxuIjsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQoKICAgICAgICBsbCBhbnMgPSAxOwogICAgICAgIGlmKCBrID09IChwcyArIG5zKSkgewogICAgICAgICAgICAvLyBpZigobnMmMSkgJiYgemVybz4wKSB7CiAgICAgICAgICAgIC8vICAgICBjb3V0PDwiMFxuIjsKICAgICAgICAgICAgLy8gICAgIHJldHVybiAwOwogICAgICAgICAgICAvLyB9CiAgICAgICAgICAgIGlmcihpLCAwLCBwcykgYW5zID0gKGFucypwb3NbaV0pJW1vZDsKICAgICAgICAgICAgaWZyKGksIDAsIG5zKSBhbnMgPSAoYW5zKm5lZ1tpXSklbW9kOwogICAgICAgICAgICBhbnMgPSAoYW5zICsgbW9kKSVtb2Q7CiAgICAgICAgICAgIGNvdXQ8PGFuczw8ZW5kbDsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQoKICAgICAgICBzb3J0KGFsbChwb3MpLCBncmVhdGVyPGxsPigpKTsKICAgICAgICBzb3J0KGFsbChuZWcpKTsKCiAgICAgICAgaWYobnMgPT0gMCkgewogICAgICAgICAgICBhbnMgPSAxOwogICAgICAgICAgICBpZnIoaSwgMCwgaykgYW5zID0gKGFucypwb3NbaV0pJW1vZDsKICAgICAgICAgICAgY291dDw8YW5zPDxlbmRsOwogICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICB9CgoKICAgICAgICBpZihwcyA9PSAwKSB7CiAgICAgICAgICAgIGlmKGsmMSkgcmV2ZXJzZShhbGwobmVnKSk7CiAgICAgICAgICAgIGlmKChrJjEpICYmIHplcm8+MCkgewogICAgICAgICAgICAgICAgY291dDw8IjBcbiI7CiAgICAgICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICAgICAgfQogICAgICAgICAgICBhbnMgPSAxOwogICAgICAgICAgICBpZnIoaSwgMCwgaykgYW5zID0gKGFucypuZWdbaV0pJW1vZDsKICAgICAgICAgICAgYW5zID0gKGFucyArIG1vZCklbW9kOwogICAgICAgICAgICBjb3V0PDxhbnM8PGVuZGw7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0KCiAgICAgICAgdmVjdG9yPGxkPiBwcmU7CgogICAgICAgIHByZS5wYigwKTsKICAgICAgICBpZnIoaSwgMCwgcHMpIHByZS5wYihwcmUuYmFjaygpICsgbG9nKHBvc1tpXSkpOwoKICAgICAgICBsZCBsZyA9IDAsIHN1bSwgbXN1bSA9IDA7IAogICAgICAgIGludCB4PS0xLCB5PS0xOwoKICAgICAgICBmb3IoaW50IGk9MDsgaTw9bnM7IGkrKykgewoKICAgICAgICAgICAgaWYoay1pPDAgKSBicmVhazsKCiAgICAgICAgICAgIGlmKCgoay1pKT5wcykgfHwgKGkmMSkpIHsKICAgICAgICAgICAgICAgIGxnICs9IGxvZygtbmVnW2ldKTsKICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICB9CgogICAgICAgICAgICBzdW0gPSBsZyArIHByZVtrLWldOwoKICAgICAgICAgICAgLy8gY291dDw8c3VtPDwiICI8PG1zdW08PGVuZGw7CgogICAgICAgICAgICBpZihtc3VtIDwgc3VtKSB7CiAgICAgICAgICAgICAgICBtc3VtID0gc3VtOwogICAgICAgICAgICAgICAgeCA9IGk7IHkgPSBrLWk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGlmKGkhPW5zKSBsZyArPSBsb2coLW5lZ1tpXSk7CiAgICAgICAgfQoKICAgICAgICAvLyBjb3V0PDx4PDwiICI8PHk8PGVuZGw7CiAgICAgICAgaWYoeD09LTEpIHsKICAgICAgICAgICAgY291dDw8MDw8ZW5kbDsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQoKICAgICAgICBhbnMgPSAxOwogICAgICAgIGlmKCh4JjEpICYmIHplcm8+MCApIHsKICAgICAgICAgICAgY291dDw8IjBcbiI7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0KICAgICAgICBpZnIoaSwgMCwgeCkgYW5zID0gKDFsbCphbnMqbmVnW2ldKSVtb2Q7CiAgICAgICAgaWZyKGksIDAsIHkpIGFucyA9ICgxbGwqYW5zKnBvc1tpXSklbW9kOwogICAgICAgIGFucyA9IChhbnMgKyBtb2QpJW1vZDsKICAgICAgICBjb3V0PDxhbnM8PGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=