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

#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vii vector<pii>
#define vll vector<pll>
#define vb vector<bool>
#define vvb vector<vb>
#define vl vector<ll>
#define endl '\n'
#define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long
#define f first
#define s second
#define mid (l+r)/2
#define mide (hi+lo)/(ll)2

using namespace std;

ll pot = (ll)1<<(ll)30;
ll global_i;
ll M = 1000000007;
int n;

struct tree
{
    ll t[2];
    tree* l;
    tree* r;
    tree(): l(NULL), r(NULL){t[0] = 0; t[1] = 0;}
};

tree* root = new tree();

tree* goL(tree* e)
{
    if(e->l == NULL)
        e->l = new tree();
    return e->l;
}

tree* goR(tree* e)
{
    if(e->r == NULL)
        e->r = new tree();
    return e->r;
}

ll get(tree* e, bool senko)
{
    if(e == NULL)
        return 0;
    return e->t[senko];
}

ll query(ll a, ll b, bool senko, tree* e = root, ll lo = 0, ll hi = pot)
{
    if(b<=a) return 0;
    if(a == lo and b == hi)
        return e->t[senko];
    ll pom1 = query(a, min(mide, b), senko, goL(e), lo, mide);
    ll pom2 = query(max(a, mide), b, senko, goR(e), mide, hi);
    return (pom1+pom2)%M;
}

void add(ll x, ll val, tree* e = root, ll lo = 0, ll hi = pot)
{
    if(lo+1 == hi)
    {
        e->t[x&(ll)1] = (e->t[x&(ll)1] + val)%M;
        return;
    }
    if(lo <= x and x < mide)
        add(x, val, goL(e), lo, mide);
    if(mide <= x and x < hi)
        add(x, val, goR(e), mide, hi);
    e->t[0] = (get(e->l, 0)+get(e->r, 0))%M;
    e->t[1] = (get(e->l, 1)+get(e->r, 1))%M; 
}


int main()
{
    turbo
    cin >> n;
    global_i = 0;
    int pom; cin >> pom;
    add(pom, 1);
    for(int i = 1; i < n; i++)
    {
        ll x; cin >> x;
        ll poms = (query(global_i, M, global_i%2) + query(0, global_i, (global_i+1)%2))%M;
        global_i = (global_i-x+M)%M;
        add((global_i+x)%M,poms);   
    }
    cout << (query(global_i, M, global_i%2)+query(0, global_i, (global_i+1)%2))%M << endl;
}