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
// Autor: Mikołaj Janusz
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    ll MODULO_BASE = 1000000007;
    
    if (n < 4500) {
        vector<ll> numbers(n);
        vector<ll> res(n);
        ll cur_sum = 0;

        for (int i = 0; i < n; i++) {
            cin >> numbers[i];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                cur_sum = (cur_sum + numbers[i-j]) % MODULO_BASE;

                if (cur_sum % 2 == 0)
                    res[i] = (res[i] + res[i-j-1]) % MODULO_BASE;
            }

            if (((cur_sum + numbers[0]) % MODULO_BASE) % 2 == 0) {
                res[i] = (res[i] + 1) % MODULO_BASE;
            }
            cur_sum = 0;
        }

        cout << res[n-1] << endl;
    } else {
        vector<ll> remainders(n);
        vector<ll> last_odd(n);
        vector<ll> dp(n+1);
        ll cur_sum = 0;
        ll temp;
        ll last_odd_index = -1;

        for (int i = 0; i < n; i++) {
            cin >> temp;
            remainders[i] = ((temp % (MODULO_BASE)) % 2);

            last_odd[i] = last_odd_index;
            if (remainders[i] % 2 != 0) {
                last_odd_index = i;
            }
        }

        dp[0] = 1;
        dp[1] = remainders[0] ^ 1;

        for (int i = 1; i < n; i++) {
            if (remainders[i] % 2 == 0) {
                dp[i+1] = (dp[i] * 2) % MODULO_BASE;
            } else {
                last_odd_index = last_odd[i];
                if (last_odd_index == -1) {
                    dp[i+1] = 0;
                } else {
                    if (last_odd_index == 0) {
                        dp[i+1] = 1;
                    } else {
                        dp[i+1] = (dp[last_odd_index] * 2) % MODULO_BASE;   
                    }
                }
            }
        }

        cout << dp[n] << endl;
    }

    return 0;
}