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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef pair<int, int> Value;
constexpr int P = 1696969;

namespace std {
    template<>
    struct hash<Value> {
        size_t operator() (const Value& x) const& {
            auto [a, b] = x;
            return (a * P) + b;
        }
    };
}

long long mod = 1000000007;


long long f(int start, int finish, vector<long long>& work, vector<long long>& v, unordered_map <Value, int>& M);

long long g(int start, int finish, vector <long long> work, vector<long long>& v, unordered_map <Value, int>& M) {    //otwarto domkniety
    if (start == finish)
        return 1;


    if (M.find({ start, finish })!=M.end())
        return M[{start, finish}];
    
    long long temp = f(start + 1, finish, work, v, M);
    M[{start, finish}] = temp;
    return temp;

}



long long f(int start, int finish, vector<long long> &work, vector<long long>& v, unordered_map <Value, int> &M) {        //domknieto domkniety
    priority_queue<int> Q;
    work[start] = (v[start]) %mod;
    if (!(work[start] % 2))
        Q.push(start);
    for (int i = start + 1; i <= finish; i++) {
        work[i] = (work[i - 1] + v[i]) % mod;
        if (!(work[i] % 2))
            Q.push(i);
    }

    if (start == finish && work[finish] % 2 == 1)
        return 0;

    long long ans = 0;

    while (!Q.empty()) {
        ans += g(Q.top(), finish, work, v, M);
        ans %= mod;
        Q.pop();
    }

    return ans;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;

    unordered_map <Value, int> M;

    vector <long long> vec(n);
    for (auto& x : vec) cin >> x;
    vector <long long> work(n);

    cout << f(0, n - 1, work, vec, M) << "\n";
}