How many different?

For the given set of n integers a[1], . . ., a[n] 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 a[1], ..., a[n] (1 ≤ n ≤ 20, -10^5 ≤ a[i] ≤ 10^5).

Output

Print the power of the set of sums of elements.

Examples