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

using namespace std;

constexpr int P = 1000*1000*1000 + 7;

struct V
{
    int v[2];
    int& operator[](int i) { return v[i]; }
    void Adjust(int x) {
        x &= 1;
        tie(v[0], v[1]) = make_tuple(v[x], v[x ^ 1]);
    }
};

struct Node
{
    Node *left, *right;
    int pri;
    int delta;
    V count, total;

    Node(Node *left, Node *right, int pri, int x, V count)
        : left(left), right(right), pri(pri), delta(x), count(count) { Update(); }

    void Update() {
        total = count;
        for (int i = 0; i < 2; ++i) {
            int j = i ^ (delta & 1);
            if (left) total[i] = (total[i] + left->total[j]) % P;
            if (right) total[i] = (total[i] + right->total[j]) % P;
        }
    }
};

class Tree
{
    typedef Node* Ptr;
    Ptr root = nullptr;

    Ptr Shift(Ptr v, int x) {
        if (v) {
            v->delta += x;
            v->count.Adjust(x);
            v->total.Adjust(x);
        }
        return v;
    }

    Ptr Merge(Ptr a, Ptr b) {
        if (!a) return b;
        if (!b) return a;
        if (a->pri < b->pri) {
            a->right = Merge(a->right, Shift(b, -a->delta));
            a->Update();
            return a;
        } else {
            b->left = Merge(Shift(a, -b->delta), b->left);
            b->Update();
            return b;
        }
    }

    pair<Ptr, Ptr> Split(Ptr v, int x)
    {
        if (!v) return pair<Ptr, Ptr>(nullptr, nullptr);
        if (x <= v->delta) {
            auto l = Split(v->left, x - v->delta);
            v->left = l.second;
            v->Update();
            return make_pair(Shift(l.first, v->delta), v);
        } else {
            auto r = Split(v->right, x - v->delta);
            v->right = r.first;
            v->Update();
            return make_pair(v, Shift(r.second, v->delta));
        }
    }

    void Add(Ptr& v, int pri, int x, V count)
    {
        if (v && pri >= v->pri) {
            count.Adjust(v->delta);
            Add(x < v->delta ? v->left : v->right, pri, x - v->delta, count);
            v->Update();
        } else {
            auto s = Split(v, x);
            v = new Node(Shift(s.first, -x), Shift(s.second, -x), pri, x, count);
        }
    }

public:
    void Add(int x, V count) { Add(root, rand(), x, count); }
    V Count() { return root->total; }
    void Shift(int x) {
        if (x == 0) return;
        auto s = Split(root, P - x);
        Shift(s.first, x);
        Shift(s.second, x - P);
        root = Merge(s.second, s.first);
    }
};

int main()
{
    int n;
    scanf("%d", &n);
    Tree tree;
    V count{{1, 0}};
    tree.Add(0, count);
    for (; n > 0; --n) {
        int x;
        scanf("%d", &x);
        tree.Shift(x);
        count = tree.Count();
        count[1] = 0;
        tree.Add(0, count);
    }
    printf("%d\n", count[0]);
    return 0;
}