Alice and Bob went trick or treating together this year, which meant that they had to divide up their candy once the night was over. To accomplish this, they divided the candy into ~N~ piles and then Alice took some subset of the piles for herself, while Bob got the rest of the piles.

Alice was happy with how this process turned out, however she now wonders how many different subsets could she have chosen in order to have more candy than Bob. Could you help her answer this difficult task?

Input Specification

The first line of input contains a single integer ~N~ ~(1 \le N \le 30)~, the number of candy piles. The next line of input contains ~N~ integers ~C_1, C_2, \ldots, C_N (1 \le C_i \le 100~ ~000)~, the number of candies in each pile. The total number of candies is guaranteed to be odd.

Output Specification

The number of different subsets that Alice could have chosen to have more candy than Bob.

Sample Input 1

1
5

Sample Output 1

1

Sample Input 2

2
3 4

Sample Output 2

2