For the given set of n integers a1, . . ., an find the number of different numbers, representing the sum of the elements of nonempty subsets of a given set. In other words, determine the power of the set of sums of elements of all kinds of nonempty subsets of a given set.

Input

First line contains number n. Second line contains numbers a1, ..., an (1 ≤ n ≤ 20, -105 ≤ ai ≤ 105).

Output

Print the power of the set of sums of elements.