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
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define N 300005
#define MOD 1000000007

long long n;
long long a[N];
long long p[N];
long long t[2*N];
unordered_set<int> us;
unordered_map<int, int> um;
vector<int> vec[2];

int binary_search(int i, int v){
    int beg = 0;
    int end = vec[i].size()-1;
    int pos = -1;
    while(beg <= end){
        int mid = (beg + end) / 2;
        if(vec[i][mid] >= v){
            end = mid - 1;
            pos = mid;
        }
        else{
            beg = mid + 1;
        } 
    }
    return pos;
}

void add(int v, int tl, int tr, int p, int u){
    if(tl == tr){
        t[v] = (t[v] + u)%MOD;
    }
    else{
        int tm = (tl+tr)/2;
        int left = v + 1;
        int right = v + (tm - tl + 1) * 2;
        if(p <= tm) add(left, tl, tm, p, u);
        else add(right, tm+1, tr, p, u);
        t[v] = (t[left] + t[right]) % MOD;
    }
}

long long sum(int v, int tl, int tr, int l, int r){
    if(r < l) return 0;
    else if(tl == l && tr == r){
        return t[v];
    }
    else{
        int tm = (tl+tr)/2;
        int left = v + 1;
        int right = v + (tm - tl + 1) * 2;
        return (sum(left, tl, tm, l, min(tm, r)) + sum(right, tm+1, tr, max(tm+1, l), r))%MOD;
    }
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    us.insert(0);
    vec[0].push_back(0);
    
    cin >> n;
    
    for(int i=0;i<n;i++){
        cin >> a[i];

        if(i != 0) p[i] = p[i-1];
        p[i] = (p[i] + a[i])%MOD;

        if(us.count(p[i]) == 0){
            us.insert(p[i]);
            vec[p[i]%2].push_back(p[i]);
        }
    }

    int pos = 0;
    
    for(int i=0;i<2;i++){
        sort(vec[i].begin(), vec[i].end());
        for(int j=0;j<vec[i].size();j++){
            um[vec[i][j]] = pos++;
        }
    }

   	long long ans = 0;
    int m = us.size();

    add(0, 0, m-1, um[0], 1);

    for(int i=0;i<n;i++){
    	ans = 0;

        if(p[i]%2 == 0){
            ans += sum(0, 0, m-1, um[0], um[p[i]]);
            ans %= MOD;
            int start_pos = binary_search(1, p[i]);
            
            if(start_pos != -1){
            	ans += sum(0, 0, m-1, um[vec[1][start_pos]], um[vec[1][vec[1].size()-1]]);
            	ans %= MOD;
            }
        }

        else{
        	ans += sum(0, 0, m-1, um[vec[1][0]], um[p[i]]);
        	ans %= MOD;
        	int start_pos = binary_search(0, p[i]);
        	
        	if(start_pos != -1){
        		ans += sum(0, 0, m-1, um[vec[0][start_pos]], um[vec[0][vec[0].size()-1]]);
            	ans %= MOD;
        	}
        }

        add(0, 0, m-1, um[p[i]], ans);
    }

    cout << ans%MOD;
    
    return 0;
}