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
#include <iostream>
#include <list>
#include <vector>
#include <assert.h>

constexpr int M = 1'000'000'007;
constexpr int N = 500'000'004;

struct tree {
    struct tree *l = nullptr;
    struct tree *r = nullptr;
    long long poss = 1;
    long long poss_children = 0;
    long long rolling = 0;

    ~tree() {
        if (l) { delete l; }
        if (r) { delete r; }
    }

    void insert(long long new_poss, long long new_rolling) {
        if (new_rolling == rolling) {
            poss += new_poss;
            poss %= M;
        } else {
            poss_children += new_poss;
            poss_children %= M;
            if (new_rolling < rolling) {
                if (l) {
                    l->insert(new_poss, new_rolling);
                } else {
                    l = new tree();
                    l->poss = new_poss;
                    l->rolling = new_rolling;
                }
            } else {
                if (r) {
                    r->insert(new_poss, new_rolling);
                } else {
                    r = new tree();
                    r->poss = new_poss;
                    r->rolling = new_rolling;
                }
            }
        }
    }

    long long eval(bool negate, long long min, long long max) {
        long long leq = less_eq_than(min);
        long long ge = greater_than(max);

        if (negate) {
            return (leq + ge) % M;
        } else {
            long long ret = (poss + poss_children - (leq + ge)) % M;
            if (ret < 0) { ret += M; }
            return ret;
        }
    }

    long long less_eq_than(long long min) {
        if (rolling == min) {
            return (poss + (l ? l->poss + l->poss_children : 0)) % M;
        } else if (rolling > min) {
            return (l ? l->less_eq_than(min) : 0) % M;
        } else { // rolling < min
            return ((r ? r->less_eq_than(min) : 0) + poss + (l ? l->poss + l->poss_children : 0)) % M;
        }
    }

    long long greater_than(long long max) {
        if (rolling == max) {
            return (r ? r->poss + r->poss_children : 0) % M;
        } else if (rolling < max) {
            return r ? r->greater_than(max) : 0;
        } else { // rolling > max
            return ((l ? l->greater_than(max) : 0) + poss + (r ? r->poss + r->poss_children : 0)) % M;
        }
    }
};

int main() {
    int n;
    std::cin >> n;

    tree haha;
    long long rolling = 0;
    for (int i = 0; ; ++i) {
        long long a;
        std::cin >> a;
        a = (a * N) % M;

        rolling = (a + rolling) % M;

        long long min = rolling - N;
        long long max = rolling;
        bool negate = min < 0;
        if (negate) {
            min = max;
            max = min + (M - N);
        }

        long long poss_new = haha.eval(negate, min, max);

        if (i == n - 1) {
            std::cout << poss_new << "\n";
            break;
        } else {
            haha.insert(poss_new, rolling);
        }
    }
}