#pragma GCC optimize("O2")
// #pragma GCC optimize("O1","O2","O3","Ofast","unroll-loops")
// #pragma GCC target("sse","sse2","sse3","sse4.1","sse4.2","avx","avx2","fma")
#include <iostream>
#include <algorithm> // for sort, mainly
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <array>
#include <string>
#include <cstdio>
#include <iterator>
#include <unordered_set>
#include <cstdint> // for int64_t, int32_t, etc
#include <queue>
#include <stack>
#include <deque>
#include <numeric> // gcd, lcm
#include <fstream>
#include <bitset> // for bitset
#include <iomanip>
#include <cassert> // for set with custom ordering
#include <type_traits> // for set with custom ordering
#include <utility> // for swap, forward, etc
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
/*
notes:
int64_t
stoi(string s) -> string to int
to_string() -> int (or else) to string
vector declaration:
vector<ll> v(n, 0)
vector<vector<ll>> v(n, vector<ll>(n, 0));
{if statement} ? {truth value} : {false value}
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
std::lcm(ll a, ll b), std::gcd(int a, int b)
cout << fixed << setprecision(n);
set with custom ordering
set<ll, decltype(&cmp)> qu(cmp);
*/
typedef int64_t ll;
const ll md = 1e9 + 7;
void solve() {
ll n, k, b;
cin >> n >> k >> b;
ll negc = 0;
vector<ll> v(n, 0);
for(ll i = 0; i < n; i++) {
cin >> v[i];
if(v[i] < 0) {
negc++;
}
}
if(negc < b) {
cout << "-1";
return;
}
if(b == n) {
// egyedi eset
// nincs pozitiv szam amit novelgessunk
// minden novelessel veszitunk a szorzat ertekebol
// ugyanazt csinaljuk, igazabol, csak forditva
// az egeszet levisszuk (-1)-re, megnezzuk, hany opearacio volt
// ha tobb mint k, szupi, visszaepitjuk oket
// ha kevesebb, szivas, nem lehet
ll down = 0;
map<ll,ll> mp;
set<ll> s;
for(ll i = 0; i < n; i++) {
down += abs(-1 - v[i]);
mp[v[i]]++;
s.insert(v[i]);
}
if(down < k) {
cout << "-1";
return;
}
// kepzeletben most az osszes -1
// vagy hat, 1, erted
// minden erteknel van egy par, ami ugy marad
for(auto & [key, val] : mp) {
//cerr << "\nkey=" << key << "; val=" << val << "; s=" << s;
if(val == 0) {
continue;
}
if(k == 0) {
break;
}
if(s.count(key) == false) {
continue;
}
// tuddjuk-e novelni a kovetkezoig
// ha nem, egyenkent mennyire tuddjuk novelni oket?
if(key == *s.rbegin()) {
//cerr << "\nall are equal, final element";
ll ext = k % val;
ll all = k / val;
//cerr << "\next=" << ext << "; all=" << all;
if(all > 0) {
mp[key + all] += val - ext;
mp[key + all + 1] += ext;
mp[key] = 0;
}else{
mp[key] -= ext;
mp[key + 1] += ext;
}
k = 0;
break;
}
ll nxt = *s.upper_bound(key);
ll dis = nxt - key;
if(k >= dis * val) {
k -= dis * val;
mp[nxt] += val;
mp[key] = 0;
s.erase(key);
}else{
//s.erase(key);
ll ext = k % val;
ll all = k / val;
if(all > 0) {
mp[key + all] += val - ext;
mp[key + all + 1] += ext;
mp[key] = 0;
}else{
mp[key] -= ext;
mp[key + 1] += ext;
}
k = 0;
break;
}
}
ll j = n-1;
for(auto it = mp.rbegin(); it != mp.rend(); it++) {
auto h = *it;
//cerr << "\nh=" << h;
for(ll i = 0; i < h.second; i++) {
v[j] = h.first;
j--;
}
}
//cerr << "\nv=" << v;
ll ans = 1;
for(ll i = 0; i < n; i++) {
if(v[i] < 0) {
ans = (ans * (v[i] * v[i+1])) % md;
i++;
}else if(v[i] >= 0) {
ans = (ans * v[i]) % md;
}
}
cout << ans;
return;
}
sort(v.begin(), v.end());
for(ll i = n - 1; i >= 0; i--) {
if(v[i] < 0 && negc > b) {
ll nd = abs(v[i]);
if(k >= nd) {
v[i] = 0;
negc--;
k -= nd;
}else{
cout << "-1";
return;
}
}
}
//cerr << "\nv=" << v;
map<ll,ll> mp;
set<ll> s;
for(ll i = 0; i < n; i++) {
if(v[i] >= 0) {
mp[v[i]]++;
s.insert(v[i]);
}
}
for(auto & [key, val] : mp) {
//cerr << "\nkey=" << key << "; val=" << val << "; s=" << s;
if(val == 0) {
continue;
}
if(k == 0) {
break;
}
if(s.count(key) == false) {
continue;
}
// tuddjuk-e novelni a kovetkezoig
// ha nem, egyenkent mennyire tuddjuk novelni oket?
if(key == *s.rbegin()) {
//cerr << "\nall are equal, final element";
ll ext = k % val;
ll all = k / val;
//cerr << "\next=" << ext << "; all=" << all;
if(all > 0) {
mp[key + all] += val - ext;
mp[key + all + 1] += ext;
mp[key] = 0;
}else{
mp[key] -= ext;
mp[key + 1] += ext;
}
k = 0;
break;
}
ll nxt = *s.upper_bound(key);
ll dis = abs(nxt - key);
if(k >= dis * val) {
k -= dis * val;
mp[nxt] += val;
mp[key] = 0;
s.erase(key);
}else{
//s.erase(key);
ll ext = k % val;
ll all = k / val;
if(all > 0) {
mp[key + all] += val - ext;
mp[key + all + 1] += ext;
mp[key] = 0;
}else{
mp[key] -= ext;
mp[key + 1] += ext;
}
k = 0;
break;
}
}
//cerr << "\nmp=" << mp;
ll j = n-1;
for(auto it = mp.rbegin(); it != mp.rend(); it++) {
auto h = *it;
//cerr << "\nh=" << h;
for(ll i = 0; i < h.second; i++) {
v[j] = h.first;
j--;
}
}
//cerr << "\nv=" << v;
ll ans = 1;
for(ll i = 0; i < n; i++) {
if(v[i] < 0) {
ans = (ans * ((v[i] * v[i+1]) % md)) % md;
i++;
}else if(v[i] >= 0) {
v[i] %= md;
ans = (ans * v[i]) % md;
}
}
cout << ans;
}
int main()
{
std::ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
solve();
return 0;
}
/*
162 = 2 * 9^2 = 2 * 3^4
81
*/