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
#include <bits/stdc++.h>

using namespace std;

int tab[300010];
long long pot[300010];
int mod=1000000007;

int main()
{
    int n;
    long long sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&tab[i]);
        sum+=tab[i];
    }
    if(sum<mod){
        bool jed=false;
        int lic=0;
        long long wynik=1;
        pot[0]=1;
        for(int i=1;i<=n;i++){
            pot[i]=pot[i-1]*2;
            pot[i]%=mod;
        }
        for(int i=1;i<=n;i++){
            if(!jed){
                if(tab[i]%2==0){
                    lic++;
                } else {
                    jed=true;
                    wynik*=pot[lic];
                    wynik%=mod;
                }
            } else {
                if(tab[i]%2==1){
                    lic=1;
                    jed=false;
                }
            }
        }
        wynik*=pot[lic-1];
        wynik%=mod;
        if(jed){
            wynik=0;
        }
        printf("%lld\n",wynik);
        return 0;
    }

    //if(n<=3000){
        long long wynik=0;
        pot[0]=1;
        long long tmps=0;
        for(int i=1;i<=n;i++){
            tmps=0;
            for(int j=i;j>0;j--){
                tmps+=tab[j];
                if(!((tmps%mod)%2)){
                    pot[i]+=pot[j-1];
                    pot[i]%=mod;
                }
            }
        }
        printf("%lld",pot[n]);
        return 0;
    //}
    return 0;
}