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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<21; 
vector<pair<ll, ll>> v;
vector<ll>s;
map<ll, int> mapa;
ll drz[2][2 * N];

void Dodaj(int d, int v, ll w)
{
    v += N;
    while(v > 0)
    {
        drz[d][v] += w;
        drz[d][v] %= M;
        v /= 2;
    }
}

int Sum(int d, int a, int b)
{
    a += N; b += N;
    ll w = drz[d][a]; if(b != a) w += drz[d][b];
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) w += drz[d][a + 1];
        if(b % 2 == 1) w += drz[d][b - 1];
        a /= 2; b /= 2; w %= M;
    }
    return w;
}

void Scale()
{
    int x = 1;
    sort(s.begin(), s.end());
    for(int i = 0; i < (int)s.size(); ++i)
    {
        if(i == 0 && s[i] % 2LL == 0LL)
        {
            ++x;
        }else
        {
            if(i != 0 && s[i] != s[i - 1])
            {
                ++x;
                if(s[i] % 2LL == s[i - 1] % 2LL)
                    ++x;
            }
        }
        //cout << s[i] << " " << x << "\n";
        mapa[s[i]] = x;
    }
    //if(mapa.find(0) != mapa.end())
        //cout << mapa[0] << "\n";
    for(int i = 0; i < (int)v.size(); ++i) { v[i].first = mapa[v[i].first]; v[i].second = mapa[v[i].second]; }
}

ll Wynik()
{
    int y;
    ll w = 0LL;
    Dodaj(0, 0, 1LL);
    for(int i = 0; i < (int)v.size(); ++i)
    {
        w = 0LL;
        y = v[i].second;
        w = Sum(y % 2, 0, y) + Sum(1 - (y % 2), y + 1, N - 1);
        w %= M;
        Dodaj(y % 2, y, w);
        //cout << i << " " << w << "\n";
    }
    return w;
}

void Solve()
{
    int n;
    ll x;
    ll su = 0LL;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> x;
        su += x;
        s.push_back(su % M);
        s.push_back(su / M);
        v.push_back(make_pair(su / M, su % M));
        //cout << v[i].first << " " << v[i].second << "\n";
    }
    Scale();
    //for(int i = 0; i < (int)v.size(); ++i)
        //cout << i << " " << v[i].first << " " << v[i].second << "\n";
    cout << Wynik() << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();

    return 0;
}