题目描述

一个集合被称之为可平分的，如果它可以被分为两部分，且两部分的元素之和相等。空集也算可平分的。

给定一个集合 $a_1,a_2,a_3,\dots, a_n$，请统计它有多少子集是可平分的。（本题中所指的集合允许元素相等）

输入格式

• 第一行：单个整数 $n$ 表示集合的大小
• 第二行：$n$ 个整数表示 $a_1,a_2,a_3,\dots, a_n$

输出格式

• 单个整数：表示可平分的子集数量。

4
2 2 4 8

4

样例解释 1

{} {2 2} {2 2 4} {2 2 4 8}

数据范围

• $30\%$ 的数据，$1\leq n\leq 10$
• $60\%$ 的数据，$1\leq n\leq 16$，$1\leq a_i\leq1000$
• $100\%$ 的数据，$1\leq n\leq 20$，$1\leq a_i\leq 10^7$