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

#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int MN=3*(int)1e5+7;
const ll p=(ll)1e9+7;
const int minn=3007;
vector <ll> skoki[minn];
ll mod2(int a, int n, ll P) //niech liczy (a^n)%P
{
    BOOST
    a=2;
    int wyn=1;
    int pom=a;
    for(int i=0; i<30; i++)
    {
        if((bool)((1 << i)& n))
            wyn= (ll) wyn * pom %P ;
        pom= (ll)pom * pom % P;
    }
    return wyn;
}
int tab[MN];
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll los(ll a, ll b)//losuje liczbê z przedzia³u [a,b]
{
    if(a>b) swap(a,b);
    unsigned long long r = rng();
    r<<=31;
    r+=rng();
    return ( (r % ( b-a+1 ) ) +a);
}
int main()
{
    bool warunek1=1, warunek2=0;
    int n;
    cin>>n;
    if(n<=3000)
        warunek2=1;
    ll sum=0;
    for(int i=0; i<n; i++)
    {
        cin>>tab[i];
        if(tab[i]>100) warunek1=0;
        sum+=tab[i];
    }
    if(warunek1 )
    {
        //ai<100)
        if((sum%p)%2==1)
        {cout<<0; return 0; }
        int k=0; ll wal=0;
        for(int i=0;i<n; i++ )
        {
            wal +=(tab[i])%2 ;
            if(wal%2==0 )
                k++;
        }
        cout<<mod2(2,k-1, p);
        return 0;
    }
    if(warunek2 )
    {
    //kwadracimy to
    ll sum =0;

        for(int i=0; i<n; i++)
        {
            sum=0;
            for(int j=i; j<n; j++)
            {
                sum+=tab[j];
                if((sum%p)%2==0)
                skoki[i].pb(j);
            }
        }
        ll wyn[minn]={0};
         for(int j=0; j<skoki[0].size(); j++)
            {
                wyn[skoki[0][j]]+=1;
            }
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<skoki[i].size(); j++)
            {
                wyn[skoki[i][j]]=(wyn[i-1]+wyn[skoki[i][j]])%p;
            }
            //for(int i=0; i<n;i++)
              //  cout<<wyn[i]<<' ';
            //cout<<"\n";
        }
       // cout<<"\n";
        cout<<wyn[n-1]%p;
        return 0;
    }
    cout<<los(0,p-1);
    return 0;
}