OI XXXIII - dys

// https://szkopul.edu.pl/problemset/problem/i1DZIWhPW7P03dKICkwxIB56/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;
constexpr int64_t MAX = 4e18;
constexpr int64_t NINF = -4e18;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

constexpr int mod = 1e9 + 7;

int64_t fast_pow(int64_t a, int64_t b) {
    int64_t res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

std::vector<int64_t> v;
int n;

bool check(int64_t s) {
    int64_t maxi = NINF;
    int64_t c = (s + 1) >> n;
    int64_t r = (s + 1) & ((1ll << n) - 1ll);

    // p == 0
    std::vector<std::vector<int64_t>> dp0(n + 1, std::vector<int64_t>(n + 1, NINF));
    dp0[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        if (r & (1ll << (i - 1))) {
            for (int j = 0; j < i; j++) {
                if (dp0[i - 1][j] != NINF) {
                    dp0[i][j] = dp0[i - 1][j] + (1ll << (i - 1 - j));
                }
            }
        } else {
            for (int j = 0; j <= i; j++) {
                dp0[i][j] = dp0[i - 1][j];
                if (j > 0 && dp0[i - 1][j - 1] != NINF) {
                    dp0[i][j] = std::max(dp0[i][j], dp0[i - 1][j - 1] + v[i - 1]);
                }
            }
        }
    }

    for (int j = 0; j <= n; j++) {
        if (dp0[n][j] != NINF) {
            maxi = std::max(maxi, dp0[n][j] + (c << (n - j)));
        }
    }

    // p > 0
    for (int p = 1; p <= n; p++) {
        if (!(r & (1ll << (p - 1)))) {
            continue;
        }
        std::vector<std::vector<int64_t>> dp(n + 1, std::vector<int64_t>(n + 1, NINF));

        std::vector<int64_t> z;
        if (p > 1) {
            z.assign(v.begin(), v.begin() + p - 1);
            std::sort(z.begin(), z.end(), std::greater<int64_t>());
        }
        std::vector<int64_t> pref(p, 0);
        for (int i = 0; i < (int)z.size(); i++) {
            pref[i + 1] = pref[i] + z[i];
        }

        for (int j = 1; j <= p; j++) {
            dp[p][j] = (1ll << (p - j)) + v[p - 1] + pref[j - 1];
        }
        for (int i = p + 1; i <= n; i++) {
            if (r & (1ll << (i - 1))) {
                for (int j = 1; j < i; j++) {
                    dp[i][j] = dp[i - 1][j] + (1ll << (i - 1 - j));
                }
            } else {
                for (int j = 1; j <= i; j++) {
                    dp[i][j] = std::max(dp[i - 1][j - 1] + v[i - 1], dp[i - 1][j]);
                }
            }
        }

        for (int j = 1; j <= n; j++) {
            maxi = std::max(maxi, dp[n][j] + (c << (n - j)));
        }
    }

    return maxi <= (s + 1);
}

void solve() {
    std::cin >> n;

    v.resize(n);

    for (auto& a : v) {
        std::cin >> a;
    }

    if (n > 59) {
        auto ans = fast_pow(2, n - 1);
        ans += v[n - 1] - 1;
        ans %= mod;
        if (ans < 0) ans = (ans + mod) % mod;
        std::cout << ans << '\n';
        return;
    }

    int64_t l = 1, r = MAX;

    while (l < r) {
        int64_t s = (l + r) / 2;
        if (check(s)) {
            r = s;
        } else {
            l = s + 1;
        }
    }

    std::cout << (l % mod) << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}