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

using namespace std;
using LL = long long;

const int MAXN = 300005, MOD = 1000000007, BASE = 524288;

int n;
int t[MAXN];
pair<int, int> permHlp[MAXN];
int perm[MAXN];

int add(int a, int b) {
  return (LL)(a + b) % MOD;
}

int tree[2][MAXN * 4];

void update(int par, int w, int val) {
  w += BASE - 1;
  tree[par][w] = add(tree[par][w], val);
  while (w != 1) {
    w /= 2;
    tree[par][w] = add(tree[par][w * 2], tree[par][w * 2 + 1]);
  }
}

int queryLess(int par, int w) {
  w += BASE - 1;
  int ret = tree[par][w];
  while (w != 1) {
    if (w % 2 == 1) {
      ret = add(ret, tree[par][w - 1]);
    }
    w /= 2;
  }
  return ret;
}

int queryGreat(int par, int w) {
  w += BASE - 1;
  // int ret = tree[par][w];
  int ret = 0;
  while (w != 1) {
    if (w % 2 == 0) {
      ret = add(ret, tree[par][w + 1]);
    }
    w /= 2;
  }
  return ret;
}

int getDpValue(int i) {
  int val = t[i];
  int valNode = perm[i];
  int ret = 0;

  if (val % 2 == 0) {
    int less = queryLess(0, valNode);
    int more = queryGreat(1, valNode);
    ret = add(less, more);
    update(0, valNode, ret);
  } else {
    int less = queryLess(1, valNode);
    int more = queryGreat(0, valNode);
    ret = add(less, more);
    update(1, valNode, ret);
  }
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &t[i]);
    t[i] = add(t[i], t[i - 1]);
    permHlp[i] = {t[i], i};
  }
  sort(permHlp + 1, permHlp + 1 + n);
  int act = 1;
  for (int i = 1; i <= n; ++i) {
    perm[permHlp[i].second] = act;
    while (i < n && permHlp[i].first == permHlp[i + 1].first) {
      i++;
      perm[permHlp[i].second] = act;
    }
    ++act;
  }

  update(0, 1, 1);
  int ret = 0;
  for (int i = 1; i <= n; ++i) {
    ret = getDpValue(i);
    // printf("%d :: %d\n", i, ret);
  }

  printf("%d\n", ret);
}