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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#define M 1000000007

using namespace std;

vector<int> a;
int n;

void load_data()
{
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++)
    {
        int q;
        cin >> q;
        a[i] = q;
    }
}

void gen_data()
{
    n = 35;
    n = 5;
    a.resize(n);
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % 6;

        if(rand()%2 == 0){
            a[i] += M-6;
        }
    }
}

int bf(int p, long long sum)
{
    int is_g;

    sum += a[p];

    long long s2 = sum % M;
    is_g = s2%2 == 0;

    if(p == n-1){
        return is_g;
    }

    long long res = 0;
    if(is_g == 1){
        res = bf(p+1, 0);
    }

    res += bf(p+1, sum);

    res %= M;
    return res;
}

vector<int> res;

int sol1(){
    res.resize(n);
    for (int i = 0; i < n; i++)
    {
        long long sum = 0;
        long long com = 0;
        for (int j = i; j >= 0; j--)
        {
                sum += a[j];
                long long s2 = sum % M;
                bool is_g = s2%2 == 0;
                if(is_g)
                {
                    if(j-1 < 0) com++;
                    else com += res[j-1];
                }

        }
        res[i] = com % M;
    }

    return res[n-1];
}

bool detect_if_small_test(){
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
    }

    return sum < M;
}

int sol_for_smal(){
    long long z = 0, o = 0;
    if(a[0]%2==0) z++;
    else o++;
    for (int i = 1; i < n; i++)
    {
        long long zn = 0, on = 0;
        if(a[i]%2 == 0)
        {
            zn = 2*z;
            on = o;
        }
        else{
            zn = o;
            on = 2*z;
        }
        z = zn %M;
        o = on %M;
    }

    return z;
}

void auto_test(){
    srand(998);
    while (true)
    {
        gen_data();
        int bfs = bf(0,0);
        int sol1s = sol1();
        int smal = sol_for_smal();
        if(bfs != sol1s || smal != sol1s){
           // cout << "Fail\n";
        } 
        cout << detect_if_small_test() << '\n';
        sol_for_smal();
    }
}

void run(){
    load_data();
    if(detect_if_small_test()){
        cout << sol_for_smal() << '\n';
    }
    else{
        cout << sol1() << '\n';
    }
}

int main()
{
    run();
}