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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

const int P = 1000000007;

int tsize;
struct V {
  LL even, odd;
};
vector<V> tree;

LL fetch_even(int a, int b, int A, int B, int p) {
  if (a <= A && B <= b) return tree[p].even;
  if (B <= a || b <= A) return 0ll;
  return (fetch_even(a, b, A, (A+B)/2, p*2) + fetch_even(a, b, (A+B)/2, B, p*2+1)) % P;
}

LL fetch_even(int a, int b) {
  return fetch_even(a, b, 0, tsize, 1);
}

LL fetch_odd(int a, int b, int A, int B, int p) {
  if (a <= A && B <= b) return tree[p].odd;
  if (B <= a || b <= A) return 0ll;
  return (fetch_odd(a, b, A, (A+B)/2, p*2) + fetch_odd(a, b, (A+B)/2, B, p*2+1)) % P;
}

LL fetch_odd(int a, int b) {
  return fetch_odd(a, b, 0, tsize, 1);
}

void insert(int a, LL pr, LL v) {
  int p = tsize + a;
  if (pr % 2 == 0) {
    tree[p].even = v;
  } else {
    tree[p].odd = v;
  }
  p /= 2;
  while (p > 0) {
    tree[p].even = (tree[p*2].even + tree[p*2+1].even) % P;
    tree[p].odd = (tree[p*2].odd + tree[p*2+1].odd) % P;
    p /= 2;
  }
}

void print_tree() {
  printf("Tree:\n");
  for (int i=1; i<tsize*2; ++i) {
    printf("%d: %lld %lld\n", i, tree[i].even, tree[i].odd);
  }
  printf("\n");
}

int main() {
  int n; scanf("%d", &n);
  vector<int> a(n);
  for (int i=0; i<n; ++i) scanf("%d", &a[i]);
  
  vector<LL> pref(n+1);
  LL sum = 0;
  for (int i=0; i<n; ++i) {
    pref[i] = sum % P;
    sum += a[i];
  }
  pref[n] = sum % P;

  vector<pair<LL, int>> idx(n+1);
  for (int i=0; i<n+1; ++i) {
    idx[i] = {pref[i], i};
  }
  sort(idx.begin(), idx.end());

  vector<int> ridx(n+1);
  for (int i=0; i<n+1; ++i) {
    ridx[idx[i].second] = i;
  }

  tsize = 1;
  while (tsize < n+1) tsize *= 2;
  tree.resize(tsize * 2, {0ll, 0ll});

  insert(0, 0, 1);
  for (int i=1; i<=n; ++i) {
//    print_tree();

    LL sol = 0;
    if (pref[i] % 2 == 0) {
      sol = fetch_even(0, ridx[i]) + fetch_odd(ridx[i], n+1);
    } else {
      sol = fetch_odd(0, ridx[i]) + fetch_even(ridx[i], n+1);
    }
    sol %= P;
    
//    printf("Insert at %d: %lld %lld\n", ridx[i], pref[i], sol);

    if (i == n) {
      printf("%lld\n", sol);
      return 0;
    }


    insert(ridx[i], pref[i], sol);
  }
}