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
#include <cstdio>
#include <cassert>
#include <set>
#include <unordered_map>

//#define MOD 11
#define MOD 1000000007LL
//           123456789
#define DMO (2LL*MOD) 

#define MAXN 300300
typedef long long ll;
ll data[MAXN];
int N;

std::set<ll> collect;   

ll tree[3000000][2];

int left(int p) { return p * 2; }
int right(int p) { return p * 2 + 1; }
int parent(int c) { return c / 2; }
const int TREEBASE = (1 << 20);

// tree[X] is the sum of all the elements in the subtree of X.
// Unmapped functions.
void add(ll val, int key, int t) { // key is between 0 and TREEBASE - 1. 
  key += TREEBASE;
  while (key) {
    tree[key][t] += val;
    tree[key][t] %= MOD;
    key /= 2;
  }  
} 

// key between 0 and TREEBASE. Return sum of leaf values from 0 to key-1 inclusive.
ll sumto(int key, int t) {
  ll res = 0;
  key += TREEBASE;
  while (key > 1) {
    if (key & 1) {
      res += tree[key-1][t];
      res %= MOD;
    }
    key /= 2;
  }
  return res;
}

// Maps a "real" number to an index in the rangetree
// (both rangetrees have the same set of indices, and the same mapping).
std::unordered_map<ll, int> mapping;

void add_mapped(ll val, ll key, int t) {
//  printf("Adding %I64d at key %I64d to tree %d\n", val, key, t);
  assert(mapping.find(key) != mapping.end()); 
  int real_key = mapping[key];
  add(val, real_key, t);
}

// Sum of the elements with keys in [from, to).
ll sum_between_mapped(ll from, ll to, int t) {
  assert(mapping.find(from) != mapping.end());
  assert(mapping.find(to) != mapping.end());
  int real_from = mapping[from];
  int real_to = mapping[to];
  return (MOD + sumto(real_to, t) - sumto(real_from, t)) % MOD;
}

ll sum_ordered_interval_mapped(ll from, ll to, int t) {
  ll res;
  if (to >= from) {
    res = sum_between_mapped(from, to, t);
  } else {
    res = (sum_between_mapped(0, to, t) + sum_between_mapped(from, DMO, t)) % MOD;
  } 
//  printf("In the ordered interval [%I64d, %I64d) in tree %d, there are %I64d total entries\n",
//    from, to, t, res);
  return res;
}

void construct_mapping() {
  int mapped_key = 0;
  for (ll key : collect) {
    assert(key >= 0);
    assert(key <= DMO);
    mapping[key] = mapped_key;
    mapped_key += 1;
  } 
}

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    int c;
    scanf("%d", &c);
    data[i] = c;
  }

  // Dry run, to collect the keys for the range trees.
  collect.insert(0); collect.insert(DMO);
  ll curadd = 0;
  for (int i = 0; i < N; ++i) {
    curadd = (DMO + curadd - data[i]) % DMO;
    assert(0 <= curadd);
    assert(curadd < DMO);
    collect.insert(curadd);
    collect.insert((curadd + MOD) % DMO);
    collect.insert((DMO - curadd) % DMO);
  }  
  construct_mapping();

  // Real run, where we fill in the range trees.
  add_mapped(1, 0, 0);  // value, key, treeparity.
  curadd = 0;
  ll newzero;
  for (int i = 0; i < N; ++i) {
    curadd = (DMO + curadd - data[i]) % DMO;
    newzero = sum_ordered_interval_mapped(curadd, (curadd + MOD) % DMO, curadd & 1) +
              sum_ordered_interval_mapped((curadd + MOD) % DMO, curadd, 1 - (curadd & 1));     
    add_mapped(newzero % MOD, curadd, curadd & 1);  
  }
  printf("%d\n", (int) (newzero % MOD)); 
}