该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

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

输出格式

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

4
2 -1 -2 1

4

样例解释

说明:

• $\{\}$ (空集)
• $\{a_1, a_2\} = \{2, -1, -2, 1\}$ 的和为 $2 + (-1) + (-2) + 1 = 0$
• $\{a_2, a_4\} = \{-1, 1\}$ 的和为 $-1 + 1 = 0$
• $\{a_1, a_3\} = \{2, -2\}$ 的和为 $2 + (-2) = 0$

数据规模与约定

• 对于 $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$