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

const int NN = 300300;
const int P = 1000000007;
int V[NN];
int F[NN];

inline int add(int a, int b) { return (a + b) % P; }

int brut(int N, int *V, int *F, int start) {
  for (int i = start; i < N; ++i) {
    int opts = 0;
    int sum = 0;
    for (int j = i; j >= 0; --j) {
      sum = add(sum, V[j]);
      if (sum % 2 == 0) {
        opts = add(opts, j > 0 ? F[j - 1] : 1);
      }
    }
    F[i] = opts;
  }
  return F[N - 1];
}

int fast(int N, int *V, int *F) {
  int SS = 0, NS = 0;
  int last = -1;

  for (int i = 0; i < N; ++i) {
    NS = add(SS, V[i]);
    if (NS == SS + V[i]) {
      SS = NS;
      if (SS % 2 == 1) {
        F[i] = 0;
      } else {
        F[i] = (last == -1) ? 1 : add(last, last);
        last = F[i];
      }
    } else {
      return brut(N, V, F, i);
    }
  }
  return F[N - 1];
}

int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &V[i]);
  }
  printf("%d\n", fast(N, V, F));
  return 0;
}