#include<iostream>
#include<map>
#define maxn 2000001
#define maxx 21
using namespace std;
int n,N,s;
int tot;
int a[maxx],ans[maxn];
map<int,int>b;
vector<int>p[maxn];
void dfs1(int x,int sum,int now){
	if(x>N){
		if(b[sum]==0){
			b[sum]=++tot;
		}
		p[b[sum]].push_back(now);
		return;
	}
	dfs1(x+1,sum+a[x],now|(1<<(x-1)));
	dfs1(x+1,sum-a[x],now|(1<<(x-1)));
	dfs1(x+1,sum,now);
}
void dfs2(int x,int sum,int now){
	if(x>n){
		int t=b[sum];
		if(t!=0){
			for(int i=0; i<p[t].size(); i++){
				ans[p[t][i]|now]=1;
			}
		}
		return;
	}
	dfs2(x+1,sum+a[x],now|(1<<(x-1)));
	dfs2(x+1,sum-a[x],now|(1<<(x-1)));
	dfs2(x+1,sum,now);
}
void init(){
	scanf("%d",&n);
	N=n/2;
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
	}
}
void fin(){
	for(int i=1; i<=(1<<n); i++){
		s+=ans[i];
	}
}
void print(){
	printf("%d",s);
}
void all_voi(){
	init();
	dfs1(1,0,0);
	dfs2(N+1,0,0);
	fin();
	print();
}
int main(){
	all_voi();
	return 0;
}

https://www.luogu.com.cn/record/90294685