#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll n;
ll num[50];
ll rec[50];

ll ans=0;
bool flag;

void solv(ll sum,int x,int s,ll cnt){
    if(sum==cnt){
        flag=true;
    }
    if(cnt>sum){
        return;
    }
    for(int i=x+1;i<=s;i++){
        if(flag){
            return;
        }
        solv(sum,i,s,cnt+rec[i]);
    }
}



void dfs(int s,int x,ll sum,int to){
    if(s==to){
        if(sum%2==1){
            return;
        }
        if(rec[s]>sum/2){
            return;
        }
        flag=false;
        solv(sum/2,0,s,0);
        if(flag){
            ans++;
        }
        return; 
    }
    for(int i=x+1;i<=n;i++){
        rec[s+1]=num[i];
        dfs(s+1,i,sum+num[i],to); 
    }
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    freopen("subsets.in","r",stdin);
    freopen("subsets.out","w",stdout);
    
    cin>>n;
    
    for(int i=1;i<=n;i++){
        cin>>num[i];
    }
    
    
    sort(num+1,num+1+n);
    
    
    for(int i=1;i<=n;i++){
        dfs(0,0,0,i); 
    }
    
    cout<<ans;
    
    
    
    return 0;
}