OI XXXIII - dys (Alt1)

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

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const ull MOD = 1000000007;

ull power(ull base, ull exp) {
    ull res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int n_eff;
vector<ull> a_eff;

bool check(ull days) {
    ull R = days + 1;
    vector<int> H;
    for (int i = 0; i < 63; ++i) {
        if ((R >> i) & 1) H.push_back(i);
    }

    ull global_max = 0;

    ull dp[66];
    bool valid[66];

    {
        for (int i = 0; i < 66; ++i) {
            dp[i] = 0;
            valid[i] = false;
        }
        valid[0] = true;

        for (int pos = 0; pos < n_eff; ++pos) {
            bool is_in_H = false;
            for (int x : H)
                if (x == pos) {
                    is_in_H = true;
                    break;
                }

            if (is_in_H) {
                for (int j = 0; j <= pos; ++j) {
                    if (valid[j]) {
                        dp[j] += (1ULL << (pos - j));
                    }
                }
            } else {
                for (int j = pos + 1; j >= 1; --j) {
                    if (valid[j - 1]) {
                        ull cand = dp[j - 1] + a_eff[pos];
                        if (!valid[j] || cand > dp[j]) {
                            dp[j] = cand;
                            valid[j] = true;
                        }
                    }
                }
            }
        }

        for (int p : H) {
            if (p >= n_eff) {
                for (int j = 0; j <= n_eff; ++j) {
                    if (valid[j]) {
                        dp[j] += (1ULL << (p - j));
                    }
                }
            }
        }

        for (int j = 0; j <= n_eff; ++j)
            if (valid[j]) global_max = max(global_max, dp[j]);
    }

    for (int h : H) {
        if (h >= n_eff) break;

        vector<ull> items_below;
        for (int i = 0; i < h; ++i)
            items_below.push_back(a_eff[i]);
        sort(items_below.rbegin(), items_below.rend());

        for (int i = 0; i < 66; ++i) {
            dp[i] = 0;
            valid[i] = false;
        }

        ull current_sum = 0;
        for (int m = 0; m <= h; ++m) {
            if (m > 0) current_sum += items_below[m - 1];

            int cnt = m + 1;
            ull val = current_sum + a_eff[h] + (1ULL << (h - m));

            dp[cnt] = val;
            valid[cnt] = true;
        }

        for (int pos = h + 1; pos < n_eff; ++pos) {
            bool is_in_H = false;
            for (int x : H)
                if (x == pos) {
                    is_in_H = true;
                    break;
                }

            if (is_in_H) {
                for (int j = 0; j <= pos + 1; ++j) {
                    if (valid[j]) {
                        dp[j] += (1ULL << (pos - j));
                    }
                }
            } else {
                for (int j = pos + 1; j >= 1; --j) {
                    if (valid[j - 1]) {
                        ull cand = dp[j - 1] + a_eff[pos];
                        if (!valid[j] || cand > dp[j]) {
                            dp[j] = cand;
                            valid[j] = true;
                        }
                    }
                }
            }
        }

        for (int p : H) {
            if (p >= n_eff) {
                for (int j = 0; j <= n_eff; ++j) {
                    if (valid[j]) {
                        dp[j] += (1ULL << (p - j));
                    }
                }
            }
        }

        for (int j = 0; j <= n_eff; ++j)
            if (valid[j]) global_max = max(global_max, dp[j]);
    }

    return global_max <= R;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<ull> input_a(n);
    int max_idx = -1;

    for (int i = 0; i < n; ++i) {
        cin >> input_a[i];
        if (input_a[i] > 0) {
            max_idx = i;
        }
    }

    if (max_idx == -1) {
        cout << 0 << endl;
        return 0;
    }

    if (max_idx + 1 > 61) {
        ull term1 = power(2, max_idx);
        ull term2 = input_a[max_idx] % MOD;
        ull ans = (term1 + term2) % MOD;
        ans = (ans + MOD - 1) % MOD;
        cout << ans << endl;
    } else {
        n_eff = max_idx + 1;
        a_eff.resize(n_eff);
        for (int i = 0; i < n_eff; ++i) {
            a_eff[i] = input_a[i];
        }

        ull low = 0, high = 4000000000000000000ULL;
        ull ans = high;

        while (low <= high) {
            ull mid = low + (high - low) / 2;
            if (check(mid)) {
                ans = mid;
                if (mid == 0) break;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        cout << (ans % MOD) << endl;
    }

    return 0;
}