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
86
#include<cstdio>
#include<cmath>
#include<vector>
#include<iostream>
#include<string> 
#include<algorithm>

using namespace std;
bool modulpo(int a, int mod){
    return (a + mod) % mod % 2 == 0;
}



int qpow(int base,int exp,int mod)
{
	long long int x=base;
	int ans=1;
	while(exp)
	{
		if(exp % 2!=0)
			ans*=x;
		ans = ans % mod;
		x*=x;
		x = x % mod;
		exp/=2;
	}
	return (mod + ans) % mod;
}

int main(){
    int mod=1000000007;
    int n;
    scanf("%d", &n);
    vector<int> a;
    a.push_back(0);
    vector<int> res(n+2);
    res[1] = 1;
    int sum = 0;
    int num;

    bool over9000 = false;
    int even = 0;
    for( int i=0; i < n; i++){
        scanf("%d", &num);
        sum += num;
        if ( sum >= mod){
            over9000 = true;
            sum = sum % mod;
        }
        a.push_back(sum);
        if ( sum %2 == 0)
            even ++;

    }
    
    if(over9000 == false){
        printf("%d", qpow(2, even, mod));
        return 0;
    
    }
    
   /* for( int i=2; i<=n; i++){
        for(int j=i; j<=n; j++){
            cout << (a[j] - a[i-1] + mod) % mod <<" ";        
        }
        cout <<endl;
    }*/
    for( int i=2; i <=n+1; i++)
    {
        for(int j=1; j <= i-1; j++){
        // lecimy po wszystkich poprzednich numerkach i spradzamy, czy mozna z nich do nas dojsc
        // jest dobrze jesli aj +  a(j+1) + a(i-1) jest ok
            if(modulpo(a[i-1] - a[j-1], mod)){
                res[i] = (res[i] + res[j]) % mod;
                //cout<< "dodalem do x" << i << " x" << j << " o wartosci " << res[j] <<endl; 
            }
        }
        
    }
    printf("%d", res[n+1]);
    return 0;     
     }
        
        
     //   aij = a[j-2] - a[i-2];