题目描述

你有一架天平和N 个砝码，这N 个砝码重量依次是W1, W2, ... , WN。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数N。 第二行包含N 个整数：W1, W2, W3, ... , WN。 对于50% 的评测用例，1 ≤ N ≤ 15。 对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过100000。

输出格式

输出一个整数代表答案。

输入样例

3
1 4 6

输出样例

10