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

#define MOD 1000000007LL

#define MID (1000000006LL / 2)
long long to_index(long long i) {
    if (i % 2 == 0) return i / 2;
    return (i - 1) / 2 + MID + 1;
}

inline long long mod(long long x) {
    return ((x % MOD) + MOD) % MOD;
}

inline long long posmod(long long x) {
    return x % MOD;
}

// struct Tree {
//     std::vector<std::pair<long long, long long>> v;
//     
//     void add(long long index, long long value) {
//         v.push_back({index, value});
//     }
// 
//     long long sum(long long index1, long long index2) {
//         long long res = 0;
//         for (auto x: v) {
//             if (index1 <= index2) {
//                 if ((index1 <= x.first) && (x.first <= index2)) res = mod(res + x.second);
//             } else {
//                 if ((index1 < x.first) || (x.first < index2)) res = mod(res + x.second);
//             }
//         }
//         return res;
//     }
// };

struct Tree {
    std::unordered_map<long long, long long> data = std::unordered_map<long long, long long>(10000000);
    long long total = 0;
    
    void add(long long index, long long value) {
        total = posmod(total + value);
        index += 1;
        while (index <= MOD) {
            data[index] = posmod(data[index] + value);
            index += index & -index;
        }
    }

    long long prefix_sum(long long index) {
        index += 1;
        if (index <= 0) return 0;
        long long res = 0;
        while (index > 0) {
            res = posmod(res + data[index]);
            index -= index & -index;
        }
        return res;
    }

    long long sum(long long index1, long long index2) {
        if (index1 <= index2) {
            return mod(prefix_sum(index2) - prefix_sum(index1 - 1));
        }
        return mod(total - prefix_sum(index1 - 1) + prefix_sum(index2));
    }
};

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    std::cin >> n;

    std::vector<long long> v(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> v[i];
    }

    Tree tree;
    tree.add(to_index(0), 1);

    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        sum = posmod(sum + v[i]);
        long long sum_index = to_index(sum);
        long long val = tree.sum(mod(sum_index - MID), sum_index);
        if (i < n - 1) {
            tree.add(sum_index, val);
        } else {
            std::cout << val;
        }
    }

    return 0;
}