Для заданного множества n целых чисел a1, . . ., an определить общее количество различных чисел, представляющих суммы элементов непустых подмножеств данного множества. Иными словами определить мощность множества сумм элементов всевозможных непустых подмножеств данного множества.

Входные данные

В первой строке задано число n. Во второй строке заданы числа a1, ..., an (1 ≤ n ≤ 20, -105 ≤ ai ≤ 105).

Выходные данные

Вывести мощность множества сумм элементов.