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
#include <iostream>
#include <vector>

namespace {
  using std::cin;
  using std::cout;

  using value_t = size_t;
  using number_t = size_t;

  using value_seq_t = std::vector<value_t>;
  using number_seq_t = std::vector<number_t>;

  inline value_t const PRIME = 1000000007;

  value_t add_mod(value_t x, value_t y) {
    value_t res = x + y;
    return res >= PRIME ? res - PRIME : res;
  }

  bool check_evenness(value_seq_t const & v, 
                      number_t beg, number_t end) {
    value_t sum = 0;
    for (size_t k = beg; k <= end; ++k) {
      sum = add_mod(sum, v[k]);
    }
    return sum % 2 == 0;
  }

  void count_mop_intervals(value_seq_t const & v, 
                           number_t beg,
                           number_seq_t & c) {    
    if (beg == v.size() - 1) {
      if (v[beg] % 2 == 0)
        c.push_back(1);
      else
        c.push_back(0);
    } else {
      number_t counter = 0;
      number_t n = v.size() - beg;
      count_mop_intervals(v, beg + 1, c);
      for (size_t k = 0; k < n - 1; ++k) {        
        if (check_evenness(v, 0, beg + k))
          counter = add_mod(counter, c[n - k - 2]); 
      }
      if (check_evenness(v, beg, v.size() - 1))   
        counter = add_mod(counter, 1);
      c.push_back(counter);
    }
  }
}

int main() {
  number_t n;
  value_t v;
  value_seq_t values;
  number_seq_t counters;

  cin >> n;
  for (size_t k = 0; k < n; ++k) {
    cin >> v;
    values.push_back(v);    
  }
  count_mop_intervals(values, 0, counters);
  cout << add_mod(counters.back(), 0);

  return 0;
}