OI XXXIII - dys (Alt2)

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

#include <bits/stdc++.h>

using namespace std;

typedef __int128_t int128;
typedef unsigned __int128 uint128;

const long long MOD = 1000000007;

struct Pile {
    long long count;
    int index;
};

bool comparePiles(const Pile& a, const Pile& b) {
    return a.count > b.count;
}

int128 countCompatible(int128 D, uint128 mask) {
    if (D < 0) return 0;

    int zeros[70];
    zeros[0] = 0;

    int limit = 63;
    int cnt = 0;
    for (int i = 0; i <= limit; i++) {
        if (!((mask >> i) & 1)) cnt++;
        zeros[i + 1] = cnt;
    }

    int128 res = 0;

    for (int k = limit; k >= 0; k--) {
        bool bit_d = (D >> k) & 1;
        bool bit_m = (mask >> k) & 1;

        if (bit_d) {
            res += ((int128)1 << zeros[k]);

            if (bit_m) return res;
        }
    }

    res++;
    return res;
}

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

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

    int n;
    cin >> n;

    vector<Pile> all_piles;
    all_piles.reserve(n);

    long long huge_ans = 0;
    bool huge_active = false;

    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        if (a == 0) continue;

        if (i + 1 > 62) {
            huge_active = true;
            long long term1 = power_mod(2, i);
            long long term2 = a % MOD;
            long long cur = (term1 + term2 - 1 + MOD) % MOD;
            huge_ans = cur;
        } else {
            all_piles.push_back({a, i + 1});
        }
    }

    sort(all_piles.begin(), all_piles.end(), comparePiles);

    int m = all_piles.size();
    int128 small_ans = 0;

    if (m > 0) {
        int128 low = 0;
        int128 high = 4000000000000000000;

        while (low <= high) {
            int128 mid = low + (high - low) / 2;
            bool ok = true;

            for (int i = 0; i < m; i++) {
                uint128 mask = 0;
                int128 current_sum = 0;

                for (int j = i; j < m; j++) {
                    mask |= ((uint128)1 << (all_piles[j].index - 1));
                    current_sum += all_piles[j].count;

                    if (current_sum > mid) {
                        ok = false;
                        break;
                    }

                    int128 bad = countCompatible(mid, mask) - 1;
                    int128 good = mid - bad;

                    if (good < current_sum) {
                        ok = false;
                        break;
                    }
                }
                if (!ok) break;
            }

            if (ok) {
                small_ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }

    long long final_res;
    if (huge_active) {
        final_res = huge_ans;
    } else {
        final_res = (long long)(small_ans % MOD);
    }

    cout << final_res << "\n";

    return 0;
}