题目描述

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

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

输入格式

• 第一行，单个整数表示 $n$
• 第二行，$n$ 个整数表示 $a_1,a_2,\dots,a_n$

输出格式

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

4
2 -1 -2 1

4

样例解释 1

{} {1 -1} {2 -2} {1 2 -1 -2}

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 5$
• 对于 $60\%$ 的数据，$1\leq n\leq 10$
• 对于 $100\%$ 的数据，$1\leq n\leq 22$
• 对于 $100\%$ 的数据，$-1,000,000\leq a_i\leq 1,000,000$