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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <vector>

using namespace std;

long modulo = 1000*1000*1000+7;

struct sufcount {
    long suffix_value;
    long comb_count;
};

long xes[300001];

int main() {
    long n;
    cin >> n;

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

    if (n <= 3000) {
        // n^2 version
        vector<sufcount> suffixes;
        long start_x = xes[0];
        sufcount s {start_x, 1};
        suffixes.push_back(s);
        for (long i = 1; i < n; ++i) {
            long x = xes[i];
            long total_paritious = 0;
            // cerr << "TABLE SO FAR: " << endl;
            for (long j = 0; j < suffixes.size(); ++j) {
                long old_suffix = suffixes[j].suffix_value;
                // cerr << old_suffix << ": " << suffixes[j].comb_count << endl;
                if (old_suffix % 2 == 0) {
                    total_paritious += suffixes[j].comb_count;
                    total_paritious %= modulo;
                }
                long new_suffix = (suffixes[j].suffix_value + x) % modulo;
                // options: add x to every suffix, or end the suffix and start new of value x
                suffixes[j].suffix_value = new_suffix;
            }
            // cerr << endl << "ADDING " << x << " WITH VALUE " << total_paritious << endl;
            sufcount fresh_suffix {x, total_paritious};
            suffixes.push_back(fresh_suffix);
        }
        long totalcount = 0;
        for (long i = 0; i < suffixes.size(); ++i) {
            if (suffixes[i].suffix_value % 2 == 0) {
                totalcount += suffixes[i].comb_count;
                totalcount %= modulo;
            }
        }
        cout << totalcount << endl;
    } else {
        // parity-only version
        long start_x = xes[0];
        long total_xes = start_x;
        bool start_parity = (start_x%2==0);
        long sofar_even;
        long sofar_odd;
        if (start_parity) {
            sofar_even = 1;
            sofar_odd = 0;
        } else {
            sofar_even = 0;
            sofar_odd = 1;
        }
        for (long i = 1; i < n; ++i) {
            long x = xes[i];
            total_xes += x;
            if (total_xes >= modulo) {
                // COPY PASTED FROM ABOVE BECAUSE WHY NOT
                // n^2 version
                vector<sufcount> suffixes;
                long start_x = xes[0];
                sufcount s {start_x, 1};
                suffixes.push_back(s);
                for (long i = 1; i < n; ++i) {
                    long x = xes[i];
                    long total_paritious = 0;
                    // cerr << "TABLE SO FAR: " << endl;
                    for (long j = 0; j < suffixes.size(); ++j) {
                        long old_suffix = suffixes[j].suffix_value;
                        // cerr << old_suffix << ": " << suffixes[j].comb_count << endl;
                        if (old_suffix % 2 == 0) {
                            total_paritious += suffixes[j].comb_count;
                            total_paritious %= modulo;
                        }
                        long new_suffix = (suffixes[j].suffix_value + x) % modulo;
                        // options: add x to every suffix, or end the suffix and start new of value x
                        suffixes[j].suffix_value = new_suffix;
                    }
                    // cerr << endl << "ADDING " << x << " WITH VALUE " << total_paritious << endl;
                    sufcount fresh_suffix {x, total_paritious};
                    suffixes.push_back(fresh_suffix);
                }
                long totalcount = 0;
                for (long i = 0; i < suffixes.size(); ++i) {
                    if (suffixes[i].suffix_value % 2 == 0) {
                        totalcount += suffixes[i].comb_count;
                        totalcount %= modulo;
                    }
                }
                cout << totalcount << endl;
                return 0;
            }
            bool parity = (x%2==0);
            long new_even = 0;
            long new_odd = 0;
            if (parity) {
                // add to previous suffix
                new_even = sofar_even;
                new_odd = sofar_odd;
                // or start a new one if prev was even
                new_even += sofar_even;
            } else {
                // add to previous suffix
                new_even = sofar_odd;
                new_odd = sofar_even;
                // or start a new one if prev was even
                new_odd += sofar_even;
            }
            sofar_even = new_even % modulo;
            sofar_odd = new_odd % modulo;
        }
        cout << sofar_even << endl;
    }

    return 0;
}