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

using namespace std;
using ll = long long int;

const int MAXN = 300010;
const ll MOD = 1000000007;



struct Node {

  ll from, to;
  ll payload;
  Node *left, *right;

  Node(ll from, ll to) : from(from), to(to), payload(0), left(nullptr), right(nullptr) {}

};


class SegmentTree {
public:
  SegmentTree(ll range) {
    ll pow = 1;
    while (pow < range) pow *= 2;
    root = new Node(0, pow);
  }

  ll sum(ll from, ll to) {
    return _sum(root, from, to);
  }

  void add(ll pos, ll value) {
    _add(root, pos, value);
  }


private:
  int pot;
  Node *root;

  ll _sum(Node *node, ll from, ll to) {
    if (!node) return 0;
    if (node->to <= from || to <= node->from) return 0;
    if (from <= node->from && node->to <= to) return node->payload;

    ll out = _sum(node->left, from, to) + _sum(node->right, from, to);
    if (out >= MOD) out -= MOD;
    return out;
  }

  void _add(Node *node, ll pos, ll value) {
    node->payload += value;
    if (node->payload >= MOD) node->payload -= MOD;

    if (node->from == pos && pos + 1 == node->to) {
      return;
    }

    int mid = (node->from + node->to) / 2;
    if (pos < mid) {
      if (!node->left) node->left = new Node(node->from, mid);
      _add(node->left, pos, value);
    } else {
      if (!node->right) node->right = new Node(mid, node->to);
      _add(node->right, pos, value);
    }
  }
};



int main() {
  int n;
  scanf("%d", &n);

  ll offset = 0;
  SegmentTree even(MOD);
  SegmentTree odd(MOD);

  ll value = 0;
  even.add(0, 1);
  for (int i = 0; i < n; i++) {
    ll a;
    scanf("%lld", &a);

    offset = (offset + MOD - a) % MOD;
    if (offset == 0) {
      value = even.sum(0, MOD);
    }
    else if (offset % 2 == 0) {
      value = (even.sum(offset, MOD) + odd.sum(0, offset)) % MOD;
    } else {
      value = (odd.sum(offset, MOD) + even.sum(0, offset)) % MOD;
    }
    if (offset % 2 == 0) {
      even.add(offset, value);
    } else {
      odd.add(offset, value);
    }
  }

  printf("%lld\n", value);
}