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

#define ll long long
#define isEven(from, to) ((((s[(to)+1]-s[(from)])%B)%2)==0)

using namespace std;

const ll B = 1000000007;

int n;
int a[300003];
ll s[300003];
ll dp[300003];
bool small;
map<ll, ll> m;

ll sumRange(int from, int to) {
  return (s[to+1] - s[from])%B;
}

ll solve(int to) {
  ll res = 0;
  if(isEven(0, to)) {
    res++;
    res %= B;
  }
  int i = to - 1;
  ll base = 0;
  int im = -1;
  ll range = a[to];
  while(i >= 0) {
    ll u = a[to];
    if((range%2) == 0) {
      ll key = small ? i : ((i*B) + range);
      auto it = m.find(key);
      if(it != m.end()) {
        res += it->second;
        res %= B;
        base += it->second;
        base %= B;
        break;
      }
      ll sol = dp[i];
      if(im == -1) {
        im = i;
      }
      base += sol;
      base %= B;
      res += sol;
      res %= B;
    }
    range += a[i];
    range %= B;
    i--;
  }
  if(im != -1) {
    ll key = small ? im : ((im * B) + sumRange(im + 1, to));
    m[key] = base;
  }
  dp[to] = res;
  return res;
}

ll solve() {
  for(int i=0;i<n;i++) {
    s[i+1] = s[i] + a[i];
  }
  small = s[n] < B;
  for(int i=0;i<n;i++) {
    solve(i);
  }
  return dp[n-1];
}

int main(int argc, char** argv) {
  scanf("%d", &n);
  for(int i=0;i<n;i++) {
    scanf("%d", &(a[i]));
  }
  ll res = solve();
  printf("%lld\n", res);
  return 0;
}