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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#pragma GCC optimize("O3")

#include<bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<long long>(a, b)(rng)

#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define f first
#define s second
#define pb push_back

#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvii vector<vii>

#define ll long long

const int N = 1e6 + 7;
const int INF = 1e9 + 7;
const int M = INF * 2;

const int T = (1 << 20);

unordered_map<int, int> mapa;

struct seg_tree{
    int tree[T + T];

    void add(int poz, int val){
        poz += T;

        tree[poz] = (tree[poz] + val) % INF;
        poz >>= 1;

        while(poz){
            tree[poz] = (tree[poz + poz] + tree[poz + poz + 1]) % INF;
            poz >>= 1; 
        }
    }

    int ask(int pocz, int kon){
        assert(pocz <= kon);

        pocz += T;
        kon += T;

        if(pocz == kon)
            return tree[pocz];
        
        int ret = (tree[pocz] + tree[kon]) % INF;
        while(pocz >> 1 != kon >> 1){
            if(!(pocz & 1))
                ret = (ret + tree[pocz + 1]) % INF;
            if(kon & 1)
                ret = (ret + tree[kon - 1]) % INF;
            pocz >>= 1;
            kon >>= 1;    
        }

        return ret;
    }

    int ask_raw(int pocz, int kon){
        if(pocz <= kon)
            return ask(pocz, kon);
        return (1ll * tree[1] + INF - ask(kon + 1, pocz - 1)) % INF;
    }
};

seg_tree DP[2];

void solve(){
    int n; cin >> n;

    vector<int> possible_sums = {0, INF};
    int pref = 0;

    vi tab(n);
    for(auto & u : tab)
        cin >> u;

    for(auto & u : tab){
        pref = (1ll * pref + u) % M;
        possible_sums.pb(pref);
        possible_sums.pb((1ll * pref + INF) % M);
    }

    sort(all(possible_sums));
    possible_sums.resize(unique(all(possible_sums)) - possible_sums.begin());
    for(int i = 0; i < sz(possible_sums); i++)
        mapa[possible_sums[i]] = i; 

    DP[0].add(0, 1);

    pref = 0;

    int SZ = sz(possible_sums);

    for(int i = 0; i < n; i++){
        pref = (1ll * pref + tab[i]) % M;
        int suma = 0;
        
        // chce zrobić kawałek który nie przekrecza sumy zakres [0, INF - 1]
        // wiec w ogólności pytam o przedziały zaczynające się w pref - [0, INF - 1]
        // czyli [pref - INF + 1, pref]

        // z jakiej parzystości prefixów? // muszę robić taki podział, żeby mieć pewność
        // że ostatni kawałek będzie parzysty w naszej metryce

        int parz = pref & 1;
        int a = mapa[(1ll * pref - INF + M) % M];
        int b =  mapa[pref];
        
        // odwarty po stronie a do b włącznie
        suma = (suma + DP[parz].ask_raw((a + 1) % SZ, b)) % INF;

        // chce zrobić ostatni kawałek taki, że zmienia parzystość, a więc jest z zakresu
        // [INF, M - 1] czyli pref ma mieć sume z zakresu pref - [INF, M - 1]
        // czyli [pref - M + 1, pref - INF]

        a = mapa[pref];
        b = mapa[(1ll * pref - INF + M) % M];

        suma = (suma + DP[parz ^ 1].ask_raw((a + 1) % SZ, b)) % INF;

        if(i == n - 1)
            cout << suma << '\n';

        DP[pref & 1].add(mapa[pref], suma);
    }
}

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

    int tests = 1;
    // cin >> tests;

    for (int i = 0; i < tests; i++)
        solve();

    return 0;
}