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
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define mod 1000000007
using namespace std;
int n;
long long a, tabwyn[300001], tab[300001], maks;
vector<pair<long long, int>> v;
int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i){
            scanf("%lld", &tab[i]);
            maks = max(maks, tab[i]);
    }

    if(maks <= 100){
            long long sumW = 0, sumALL = 1, sum = 0;
            for(int i = 1; i <= n; ++i){
                    a = tab[i];
                    sum += tab[i];
                    if(sum&1){
                            sumW = 0;
                            continue;
                    }
                    sumW = sumALL;
                    sumALL += sumW;
                    sumW %= mod;
                    sumALL %= mod;
            }
            printf("%lld", sumW);
    }
    else{
            v.push_back(make_pair(0, 0));
            tabwyn[0] = 1;

            for(int i = 1; i <= n; ++i){
                    a = tab[i];

                    bool b = 0;

                    for(int j = 0; j < (int) v.size(); ++j){
                            v[j].first += a;
                            v[j].first %= mod;

                            if(v[j].first&1) continue;

                            tabwyn[i] += tabwyn[v[j].second];
                            tabwyn[i] %= mod;
                            b = 1;
                    }

                    if(b) v.push_back(make_pair(0, i));
            }

            printf("%lld", tabwyn[n]);
    }
    return 0;
}