题目描述

给定 n 个数字 a1,a2,,…,an。请统计能从 1 到 n 中，选出多少种不同的下标子集，使得这些下标对应的数字之和等于 0。

注意空集与全集也是子集中的一种。

输入格式

第一行，单个整数表示 n

第二行，n个整数表示 a1,a2,…,an

输出格式

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

数据范围

对于 30% 的数据，1≤n≤5

对于 60%的数据，1≤n≤10

对于 100%的数据，1≤n≤22

对于 100%的数据，−1,000,000≤ai≤1,000,000

输入输出样例：

样例解释：

{}

{1 -1}

{2 -2}

{1 2 -1 -2}