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
87
88
89
90
91
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

using namespace std;

const int p = 1000000007;

vector<int> v;
vector<int> sumtab(300005, -1);
int n;
//long long result = 0;

//char s[20];


/*
void print(int to_pos)
{
        if (to_pos < n) {
                printf("c");
        }
        printf("(");
        for(int i = 0; i < to_pos; ++i) {
                printf(" %d", v[i]);
                if (s[i] == 1) {
                        printf(")(");
                }
        }
        printf(")\n");
}
*/

inline bool is_mop(int x)
{
        return (x % 2) == 0;
}

int gen(int pos, int sum)
{
        int x, y;

        sum = (sum + v[pos]) % p;

        if (pos == n-1) {
                if (is_mop(sum)) {
//                        print(n);
//                        result = (result+1) % p;
                        return 1;
                } else {
                        return 0;
                }
        }
        
        x = 0;
        if (is_mop(sum)) {
//                s[pos] = 1;
                if (sumtab[pos] == -1) {
                        x = gen(pos+1, 0);
                        sumtab[pos] = x;
                } else {
//                        result = (result + sumtab[pos]) % p;
                        x = sumtab[pos];
                }
        }
//        s[pos] = 0;
        y = gen(pos+1, sum);
        return (x + y) % p;
}



int main()
{
        int x;

        scanf("%d\n", &n);

        for(int i = 0; i < n; ++i) {
                int x;

                scanf("%d", &x);
                v.push_back(x);
        }

        x = gen(0, 0);
        printf("%d\n", x);
 
        return 0;
}