题目描述

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

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

输入

第一行：单个整数 $n$ 表示集合的大小

第二行：$n$ 个整数表示 $a_1,a_2,a_3,\dots, a_n$

输出

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

样例输入 #1

4
2 2 4 8

样例输出 #1

4

{}

{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$