균형 잡힌 소 부분집합

축산업자 John은 소 $N$마리를 기르고 있으며 ($2 \le N \le 20$), $i$번 소는 하루에 우유를 $M(i)$단위 생산한다 ($1 \le M(i) \le 10^8$).

John은 새 착유기를 헛간에 설치했는데, 이 기계는 헛간 왼쪽에 있는 소들의 우유 생산량 총합이 오른쪽에 있는 소들의 총합과 정확히 같을 때만 정상 작동한다.

소들의 부분집합을 두 그룹으로 나누어 각 그룹의 우유 생산량 총합을 같게 만들 수 있으면, 그 부분집합을 균형 잡힌(balanced) 부분집합이라고 하자. $N$마리 소의 부분집합 중 균형 잡힌 것이 몇 개인지 구하여라.

첫째 줄에 정수 $N$이 주어진다.

다음 $N$개의 줄 중 $i+1$번째 줄에는 $M(i)$가 주어진다.

균형 잡힌 소 부분집합의 개수를 한 줄에 출력한다.