#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[30],f[30],ff[3000010],ans,cnt;
vector <int> v;
map <int,int> mp;
void find_ans(){
//           for(int i=1;i<=n;i++){
//               if(f[i]==1){
//                   cout<<a[i]<<" ";
//               }
//           }
//           cout<<endl;
    int sum=0,las=0;
    v.clear();
    for(int i=1;i<=n;i++){
        if(f[i]==1) sum+=a[i],las=i;
    }
//    cout<<sum<<endl;
    if(sum%2==0&&sum!=0){
        v.push_back(sum/2);
        mp.clear();
        for(int i=0;i<sum/2;i++){
            ff[i]=0;
        }
        cnt=0;
        mp[sum/2]=++cnt;
        ff[cnt]=1;
//        cout<<mp[a[las]]<<endl;
        for(int i=1;i<=n;i++){
            if(f[i]==0) continue;
            if(i==las) break;
            int p=v.size();
            for(int j=0;j<p;j++){
                int y=v[j]-a[i];
//                if(y==6){
//                    cout<<v[j]<<" "<<a[i]<<endl;
//                }
                if(!mp.count(y)&&y>=0){
                    mp[y]=++cnt;
//                    cout<<y<<" ";
                    ff[cnt]=1;
                    if(y>=a[i]){
                        v.push_back(y);
                    }
                }
            }
        }
        if(ff[mp[a[las]]]==1){
           ans++; 
//           for(int i=1;i<=n;i++){
//               if(f[i]==1){
//                   cout<<a[i]<<" ";
//               }
//           }
//           cout<<endl;
        }
    }
}
void check(int x){
    if(x==n+1){
        find_ans();
        return;
    }
    f[x]=1;
    check(x+1);
    f[x]=0;
    check(x+1);
}
signed main(){
    freopen("subsets.in","r",stdin);
    freopen("subsets.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    check(1);
    cout<<ans<<endl;
}