说明

给定 几 个数字 a1,a2,...,an，请统计能从 1到 n 中，选出多少种不同的下标子集，使得这些下标对应的数字之和等于 0。
注意空集与全集也是子集中的一种。

输入格式

第一行，单个整数表示 n
第二行，几 个整数表示 a1,a2,...,an

输出格式

单个整数：表示归零子集的数量。

样例

4
2 -1 -2 1

4

提示

数据范围：

对于 30% 的数据，1 ≤ n≤5
对于 60% 的数据，1<n ≤  10
对于 100% 的数据，1≤n ≤  22
对于 100% 的数据，-1,000,000 ≤  ai ≤  1,000,000

样例1说明：
{}
{1 -1}
{2 -2}
{1 2 -1 -2}