题目描述

我们定义一个奶牛集合 $S$ 是平衡的，当且仅当满足以下两个条件：

• $S$ 非空。
• $S$ 可以被划分成两个集合 $A,B$，满足 $A$ 里的奶牛产奶量之和等于 $B$ 里的奶牛产奶量之和。划分的含义是，$A\cup B=S$ 且 $A\cap B=\varnothing$。

现在给定大小为 $n$ 的奶牛集合 $S$，询问它有多少个子集是平衡的。请注意，奶牛之间是互不相同的，但是它们的产奶量可能出现相同。

输入格式

第一行一个整数 $n$，表示奶牛的数目。

第 $2$ 至 $n+1$ 行，每行一个数 $a_i$，表示每头奶牛的产奶量。

输出格式

输出一个数表示方案总数。

4 
1 
2 
3 
4

3

共存在三种方案。集合 $\{1,2,3\}$ 可以划分为 $\{1,2\}$ 与 $\{3\}$；集合 $\{1,3,4\}$ 可以划分为 $\{1,3\}$ 与 $\{4\}$；集合 $\{1,2,3,4\}$ 可以划分为 $\{1,4\}$ 与 $\{2,3\}$，共 $3$ 种子集。

数据范围/提示

对于全部数据，保证 $1\le n\le 20$，$1\le a_i\le 10^8$。