#include<bits/stdc++.h>
using namespace std;
int n,a[25],p,t,sm,as;
map<int,int>mp;
map<int,bool>pm;
vector<int>v[1050000];
inline void dfs(int x,int s,int sx){
    if(s+s>sm) return;
    if(x==n+1){
        if(!s) return;
        p=mp[s];
        if(p) v[p].push_back(sx);
        else mp[s+a[x]]=++t,v[t].push_back(sx);
        return;
    }
    dfs(x+1,s+a[x],sx+(1<<(x-1)));
    dfs(x+1,s,sx);
    return;
}
int main(){
    freopen("subsets.in","r",stdin);
    freopen("subsets.out","w",stdout);
    cin>>n;
    for(register int i=1;i<=n;i++) cin>>a[i],sm=sm+a[i];
    dfs(1,0,0);
    for(register int i=1;i<=t;i++) for(register int j=0;j<v[i].size();j++) for(register int k=j+1;k<v[i].size();k++)
        if((v[i][j]&v[i][k])==0&&!pm[v[i][j]|v[i][k]]) as++,pm[v[i][j]|v[i][k]]=1;
    cout<<as;
    return 0;
}