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