#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int M=(1<<20)+10,N=1001;
const int mod=1e9+7;
int n,a[N],ans;
struct node{int x,y;}b[M];
bool chk[M];
bool cmp(node a,node b){return a.x<b.x;}

signed main(){
    freopen("subsets.in","r",stdin);
    freopen("subsets.out","w",stdout);
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",a+i);
    }
    for(int i=0;i<(1<<n);i++){
        int sum=0;
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                sum+=a[j];
            }
        }        
        b[i]=node{sum,i};
    }
    sort(b+0,b+(1<<n),cmp);
    int l=0,r=0;
    while(1){
        while(r<(1<<n)-1&&b[r+1].x==b[l].x)r++;
        for(int i=l;i<=r;i++){
            for(int j=l;j<i;j++){
                if((b[i].y&b[j].y)==0&&!chk[b[i].y|b[j].y]){
                    ans++;
                    chk[b[i].y|b[j].y]=1;
                }
            }
        }
        if(r==(1<<n)-1)break;
        else l=r+1;
    }
    printf("%lld\n",ans);
    return 0;
}