题目描述

你有 n 个重量不同的砝码和一个天平，每个砝码可以放在左盘或者右盘或者不放。

砝码重量为 w₁,w₂,…,wₙ。

问有多少种放置砝码的方式，使得天平平衡？（两边都不放任何砝码也算一种平衡方式）

输入格式

第 1 行，1 个正整数 n。

第 2 行，n 个正整数 w₁,w₂,…,wₙ，以空格分隔。

输出格式

输出使得天平平衡的放置方案数。

输入样例 #1

5
1 2 3 5 6

输出样例 #1

13

输入样例 #2

1
1

输出样例 #2

1

输入样例 #3

2
1 1

输出样例 #3

3

数据范围与约定

1 ≤ n ≤ 12，1 ≤ wᵢ ≤ 100