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 <iostream>
using namespace std;

const int maxN = 3e5+7;
const int modulo = 1e9+7;

int a[maxN];
long long sumpref[maxN];
long long ans[maxN];

bool czyMozna(int start, int ending)
{
    if(((sumpref[ending] - sumpref[start-1]) % modulo) % 2 == 0)
        return true;
    else
        return false;
}

void solve_a(int n)
{
    int nieparzyste = 0, zeros = 0;
    long long my_ans = 1;

    for(int i = 1; i <= n; i++)
        if(a[i] % 2 == 1)
            nieparzyste++;

    if(nieparzyste % 2 == 1) {
        cout << 0;
        return;
    }

    for(int i = 1; i <= n; i++) {
        if(a[i] % 2 == 0)
            zeros++;
        else {
            i++;
            while(a[i] % 2 == 0) {
                i++;
            }
            zeros++;
        }
    }

    for(int i = 1; i < zeros; i++)
        my_ans = (my_ans * 2) % modulo;

    cout << my_ans;
}

void solve()
{
    int n, max_a = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        max_a = max(max_a, a[i]);
    }

    if(max_a <= 1000) {
        solve_a(n);
        return;
    }

    for (int i = 1; i <= n; i++)
        sumpref[i] = sumpref[i-1] + a[i];

    ans[0] = 1;
    for(int start = 1; start <= n; start++)
        for(int ending = start; ending <= n; ending++)
            if (czyMozna(start,ending))
                ans[ending] = (ans[ending] + ans[start-1]) % modulo;

    cout << ans[n];
}

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

    solve();

    return 0;
}