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

using namespace std;

#define ULL unsigned long long
#define P 1000000007

int n;
ULL val;

int main() {

   cin >> n;

   if(n <= 3000) {
   // n <= 3000
   cin >> val;
   
   vector<ULL> res = {1};
   vector<ULL> sums = {0};
   res.reserve(n + 2);
   sums.reserve(n + 2);

   res.push_back(1 - (val % 2));
   sums.push_back(val);

   auto segsum = [&] (int i, int j) {
      return sums[j] - sums[i];
   };

   for(int i = 1; i < n; i++) {
      cin >> val;
      sums.push_back((sums.back() + val) % P);
      ULL valres = 0;
      for(int j = 0; j < res.size() - 1; j++) {
         if((segsum(j, i + 1) % P) % 2 == 0) {
            valres += res[j];
            valres %= P;
         }
      }
      if(val % 2 == 0) {
         valres += res.back();
         valres %= P;
      }
      res.push_back(valres);
   }

   // for(int i = 0; i < n + 1; i++) cout << res[i] << ' ';
   // cout << endl;

   cout << res.back() << endl;

   return 0;
   }

   // a_i <= 100
   ULL dp[2][2];
   cin >> val;
   dp[0][0] = 0;
   dp[0][1] = 0;
   if(val % 2 == 0) {
      dp[1][0] = 1;
      dp[1][1] = 0;
   } else {
      dp[1][0] = 0;
      dp[1][1] = 1;
   }

   int i, j;
   for(i = 1; i < n; i++) {
      cin >> val;
      // cout << val % 2 << endl;
      j = i % 2;
      // cout << "pre" << endl;
      // cout << dp[j][0] << ' ' << dp[j][1] << endl;
      dp[1 - j][0] = dp[j][val % 2];
      dp[1 - j][1] = dp[j][1 - (val % 2)];
      dp[1 - j][val % 2] += dp[j][0];
      dp[1 - j][val % 2] %= P;
      // cout << "post" << endl;
      // cout << dp[1 - j][0] << ' ' << dp[1 - j][1] << endl;
   }

   j = i % 2;
   cout << dp[j][0] << endl;

}