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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
using namespace std;
typedef intmax_t I;
constexpr I inf = 1e18;
typedef pair<I, I> II;
typedef double F;

#define debug_printable(template_thingies, type, start, printer, stop) \
  template <template_thingies>                                         \
  ostream &operator<<(ostream &o, const type &v) {                     \
    for (auto i = (o << start, v.begin()); i != v.end(); ++i)          \
      (i != v.begin() && (o << ", ")), o << printer;                   \
    return o << stop;                                                  \
  }
#define comma ,
debug_printable(typename T, vector<T>, "[", *i, "]");
debug_printable(typename T comma size_t N, array<T comma N>, "<", *i, ">");
debug_printable(typename T, set<T>, "{", *i, "}");
debug_printable(typename T comma typename U, map<T comma U>, "{",
                i->first << ": " << i->second, "}");
template <typename T, typename U>
ostream &operator<<(ostream &o, pair<T, U> p) {
  return o << "(" << p.first << ", " << p.second << ")";
}

constexpr I p = 1e9 + 7;

I sub(I a, I b) { return (2 * p + a - b) % (2 * p); }
bool ok(I x) { return x % 2 == (x < p ? 0 : 1); }

template <typename T>
struct point_tree_t {
  I n, w;
  vector<I> v;
  point_tree_t(I n) : n(n), w(1 << __lg(2 * n - 1)) { v.assign(2 * w, 0); }
  void set(I i, T x) {
    for (i += w, v[i] = x, i /= 2; i > 0; i /= 2)
      v[i] = v[2 * i] + v[2 * i + 1];
  }
  T get(I i) { return v[w + i]; }
  T get(I i, I j) {
    if (j < i) return 0;
    if (i == j) return get(i);
    i += w, j += w;
    T c = v[i] + v[j];
    for (; i / 2 != j / 2; i /= 2, j /= 2) {
      if (i % 2 == 0) c = c + v[i + 1];
      if (j % 2 == 1) c = c + v[j - 1];
    }
    return c;
  }
};

template <typename T>
struct point_tree {
  I n, w;
  unordered_map<I, I> v;
  // set<I> keys;
  // map<I, I> bk;
  vector<I> keys;
  point_tree_t<T> tree;
  point_tree(vector<T> keys) : keys(keys), tree(keys.size()) {
    // v.assign(2 * w, combine.neutral);
  }
  void set(I i, T x) {
    I j = lower_bound(keys.begin(), keys.end(), i) - keys.begin();
    // cout << keys << " " << i << " -> " << j << endl;
    tree.set(j, x);
  }
  // T get(I i) {
  //   I j = lower_bound(keys.begin(), keys.end(), i) - keys.begin();
  //   // return bk[i];
  //   return tree.get(j);
  // }
  T get(I i, I j) {
    I new_i = lower_bound(keys.begin(), keys.end(), i) - keys.begin();
    I new_j = upper_bound(keys.begin(), keys.end(), j) - keys.begin() - 1;
    // cout << keys << " " << i << " " << j << " -> " << new_i << " " << new_j
    //      << endl;
    return tree.get(new_i, new_j);
  }
};

// template <typename T>
// ostream &operator<<(ostream &o, point_tree<T> &v) {
//   o << "{";
//   for (auto it = v.keys.begin(); it != v.keys.end(); ++it) {
//     if (it != v.keys.begin()) o << ", ";
//     o << *it << ": " << v.get(*it);
//   }
//   o << "}";
//   return o;
// }

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  I n;
  cin >> n;
  vector<I> v(n + 1);
  for (I i = 1; i <= n; ++i) cin >> v[i];

  vector<I> w(n + 1);
  for (I i = 1; i <= n; ++i) w[i] = (w[i - 1] + v[i]) % (2 * p);

  // cout << w << "\n";

  vector<I> keys = w;
  keys.push_back(-8 * p);
  keys.push_back(8 * p);
  sort(keys.begin(), keys.end());
  // vector<II> w0 = {{0, 0}}, w1;
  point_tree<I> w0(keys), w1(keys);

  w0.set(0, 1);
  // cout << w0.v << endl;
  // cout << w0.n << " " << w0.w << endl;

  vector<I> d(n + 1);
  d[0] = 1;
  for (I i = 1; i <= n; ++i) {
    // for (I j = 0; j < i; ++j) {
    //   // cout << i << " " << j << " " << sub(w[i], w[j]) << " "
    //   //      << ok(sub(w[i], w[j])) << endl;
    //   if (ok(sub(w[i], w[j]))) {
    //     d[i] = (d[i] + d[j]) % p;
    //   }
    // }
    auto &w_same = (w[i] % 2 == 0 ? w0 : w1);
    auto &w_other = (w[i] % 2 == 0 ? w1 : w0);

    // I a = w[i];
    // for (auto [b, b_i] : w_same) {
    //   if ((a - p < b && b <= a) || (p + a + 1 < b)) d[i] = (d[i] + d[b_i]) %
    //   p;
    // }
    // for (auto [b, b_i] : w_other) {
    //   if (!((a - p < b && b <= a) || (p + a + 1 < b)))
    //     d[i] = (d[i] + d[b_i]) % p;
    // }
    I a = w[i];

    d[i] += w_same.get(a - p + 1, a);
    d[i] += w_same.get(p + a + 1, 2 * p - 1);
    d[i] %= p;

    d[i] += w_other.get(0, 2 * p - 1);
    d[i] -= w_other.get(a - p + 1, a);
    d[i] -= w_other.get(p + a + 1, 2 * p - 1);
    d[i] %= p;

    // cout << a << " " << w_same << " " << w_other << " " << d[i] << endl;
    // cout << w_same.v << endl;
    // w_same.push_back({w[i], i});
    // sort(w_same.begin(), w_same.end());
    w_same.set(w[i], w_same.get(w[i], w[i]) + d[i]);
  }
  // cout << d << endl;
  cout << d[n] << endl;
}