Farmer John имеет $N$ коров, $2 \le N \le 20$; корова $i$ даёт $M(i)$ единиц молока ежедневно ($1 \le M(i) \le 100,000,000$). Для упрощения ежедневного доения он поставил новую машину в амбаре. Но она слишком чувствительна: работает только при точно одинаковом общем надое коров слева и справа!

Назовём подмножество «сбалансированным», если его можно разделить на две группы с равным надоем. Только такое подмножество запускает машину, и FJ хочет знать их количество среди $N$ коров. Найдите его.

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

• Строка 1: целое $N$.
• Строки 2..1+$N$: строка $i+1$ содержит $M(i)$.

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

• Строка 1: число сбалансированных подмножеств.

Примеры

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

4
1
2
3
4

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

3

Примечание

Четыре коровы дают 1, 2, 3 и 4 единицы молока.

Три сбалансированных подмножества: $\{1,2,3\}$ делится на $\{1,2\}$ и $\{3\}$; $\{1,3,4\}$ на $\{1,3\}$ и $\{4\}$; $\{1,2,3,4\}$ на $\{1,4\}$ и $\{2,3\}$.

Автор задачи: Neal Wu, 2012