1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

#define boost                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)

const int MOD = 1e9 + 7;

unordered_map<int, int> tlumacz_z_tybetyjskiego_na_polski(vector<int> v) {
    unordered_map<int, int> szkalar;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int i = 0; i < v.size(); ++i) {
        szkalar[v[i]] = i;
    }
    return szkalar;
}

class SegmentTree{
private:
    static const int BASE = 1<<19;
    vector<int> tree;
public:
    SegmentTree() {
        tree = vector<int>(BASE<<1, 0);
    }

    void insert(int pos, int val) {
        int node = BASE + pos;
        while(node > 0) {
            tree[node] += val;
            if (tree[node] >= MOD) tree[node] -= MOD;
            node >>= 1;
        }
    }

    int query(int l, int r) {
        l += BASE, r += BASE;
        int res = tree[l];
        if (r > l) res = (res + tree[r]) % MOD;

        while (l + 1 < r) {
            if (l % 2 == 0) {
                res += tree[l + 1];
                if (res >= MOD) res -= MOD;
            }

            if (r % 2 == 1) {
                res += tree[r - 1];
                if (res >= MOD) res -= MOD;
            }

            l >>= 1; r >>= 1;
        }
        return res;
    }
};

int solve(const vector<int> &a) {
    const int n = a.size();

    vector<int> sums(n+1);
    for (int i = 1; i <= n; ++i) {
        sums[i] = sums[i - 1] + a[i - 1];
        if (sums[i] >= MOD) sums[i] -= MOD;
    }

    unordered_map<int, int> tlumacz = tlumacz_z_tybetyjskiego_na_polski(sums);
    int max_tree_idx = tlumacz.size();

    SegmentTree sum_dp[2];
    sum_dp[0].insert(0, 1);

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        int my_tree_idx = tlumacz[sums[i]];

        int my_parity = sums[i] % 2;

        res = sum_dp[my_parity].query(0, my_tree_idx) + sum_dp[my_parity ^ 1].query(my_tree_idx + 1, max_tree_idx);
        if (res >= MOD) res -= MOD;

        sum_dp[my_parity].insert(my_tree_idx, res);
    }

    return res;
}

int main() {
    boost;
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    cout << solve(a) << '\n';
    return 0;
}