题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，你可以任选其中若干个数组成一个新的可重子集，请计算有多少种选择可以使得组成的新子集元素之和大于 $0$。

输入格式

输入共两行：
第一行，单个正整数 $n$；
第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

单个整数表示方案数。

输入输出样例 #1

输入 #1

3
-1 -2 4

输出 #1

4

说明/提示

数据范围

对于 $50\%$ 的数据，$1 \leq n \leq 20$，$-1000\leq a_i\leq 1000$；
对于 $100\%$ 的数据，$1 \leq n \leq 40$，$-10^9\leq a_i\leq 10^9$。