У Фермера Джона есть N cows (2 <= N <= 20), и корова I производит M(i) единиц молока ежедневно (1 <= M(i) <= 100,000,000). ФД хочет рационализировать процесс ежедневной дойки коров, поэтому он установил новый доильный аппарат в амбаре. Есть одно НО – аппарат работает, только если коровы на левой стороне амбара имеют такое же общее количество молока, как и коровы на правой стороне амбара.
Назовем подмножество коров «сбалансированным», если оно может быть разбито на две группы, имеющие равные суммарные надои молока.
ФД хочет, чтобы Вы посчитали, сколько подмножеств из его N коров сбалансированы.
PROBLEM NAME: subsets
Формат входных данных
* Строка 1: Целое N.
* Строки 2..1+N: Строка i+1 содержит M(i).
Формат выходных данных
* Строка 1: Количество сбалансированных подмножеств коров.
Примечание
Подмножество {1,2,3} может быть разбито на {1,2} и {3}. Подмножество {1,3,4} может быть разбито на {1,3} и {4}. Подмножество {1,2,3,4} может быть разбито на {1,4} и {2,3}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
2
3
4
|
3
|