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

#define ull uint64_t
#define MODULO 1000000007
ull PowMod(ull n) {
   // https://stackoverflow.com/a/24967040
   ull ret = 1;
   ull a = 2;
   while (n > 0) {
      if (n & 1)
         ret = ret * a % MODULO;
      a = a * a % MODULO;
      n >>= 1;
   }
   return ret;
}

int main() {
   // freopen("pan0.in", "r", stdin);
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int mod = 1000000007;
   int n;
   cin >> n;
   int64_t total = 0;
   int even_count = 0;
   vector<int> tab(n);
   for (auto& a : tab) {
      cin >> a;
      total += a;
      if (total % 2 == 0)
         even_count++;
   }

   if (total < mod) {
      // code for a_i <= 100, so range-sums are below modulo and parity never switches
      int res = 0;
      if (total % 2 == 0) {
         res = PowMod(even_count - 1);
      }
      cout << res << endl;
      return 0;
   }

   // simple n**2 approach, possible starting point for something better
   vector<int> dp(n + 1);
   dp[0] = 1;
   for (int c = 1; c < dp.size(); c++) {
      int x = 0;
      int64_t sm = 0;//tab[c-1];
      for (int p = c - 1; p >= 0; p--) {
         sm += tab[p];
         if ((sm % mod) % 2 == 0) {
            x = (x + dp[p]) % mod;
         }
      }
      dp[c] = x;
   }
   cout << dp.back() << endl;
}