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

using ll = long long;

constexpr int mod = 1'000'000'007;

class tree {
public:
  tree(int n) {
    for (size = 1; size < n; size *= 2);
    v.resize(2*size);
  }

  void add(int x, ll val) {
    for (x += size; x; x /= 2) {
      v[x] = (v[x] + val) % mod;
    }
  }

  ll get(int p, int q) { // [p; q)
    if (p == q) {
      return 0;
    }
    return _get(size + p, size + q);
  }

private:
  int size;
  vector<ll> v;

  ll _get(int p, int q) {
    if (p + 1 == q) {
      return v[p];
    }
    if (p % 2) {
      return (v[p] + _get(p+1, q)) % mod;
    }
    if (q % 2) {
      return (_get(p, q-1) + v[q-1]) % mod;
    }
    return _get(p / 2, q / 2);
  }
};

int main() {
  int n;
  scanf("%d", &n);
  vector<ll> a(n), v[2];
  v[0].push_back(0);
  ll s = 0;
  for (auto &i : a) {
    scanf("%lld", &i);
    s = (s + i) % mod;
    v[s%2].push_back(s);
  }
  for (auto &i : v) {
    sort(i.begin(), i.end());
  }
  vector<tree> T{tree(v[0].size()), tree(v[1].size())};
  T[0].add(0, 1);
  s = 0;
  ll res = 0;
  for (auto i : a) {
    s = (s + i) % mod;
    int b = s % 2;
    int pos = lower_bound(v[b].begin(), v[b].end(), s) - v[b].begin();
    int pos2 = lower_bound(v[!b].begin(), v[!b].end(), s) - v[!b].begin();
    res = (T[b].get(0, pos + 1) + T[!b].get(pos2, v[!b].size())) % mod;
    T[b].add(pos, res);
  }
  printf("%lld\n", res);
}