Farmer John có $N$ con bò, $2 \le N \le 20$; bò $i$ mỗi ngày sản xuất $M(i)$ đơn vị sữa ($1 \le M(i) \le 100,000,000$). Để đơn giản hóa vắt sữa hằng ngày ông lắp máy mới trong chuồng. Nhưng nó quá nhạy: chỉ hoạt động nếu tổng sữa của bò bên trái và phải bằng nhau chính xác!

Tập con «cân bằng» nếu chia được thành hai nhóm có sản lượng sữa bằng nhau. Chỉ tập cân bằng làm máy chạy, nên FJ muốn biết số tập con cân bằng của $N$ bò. Hãy tính.

Dữ liệu vào

• Dòng 1: số nguyên $N$.
• Dòng 2..1+$N$: dòng $i+1$ chứa $M(i)$.

Dữ liệu ra

• Dòng 1: số tập con cân bằng.

Ví dụ

Dữ liệu vào 1

4
1
2
3
4

Dữ liệu ra 1

3

Ghi chú

Bốn con bò sản xuất 1, 2, 3, 4 đơn vị.

Ba tập cân bằng: $\{1,2,3\}$ chia thành $\{1,2\}$ và $\{3\}$; $\{1,3,4\}$ thành $\{1,3\}$ và $\{4\}$; $\{1,2,3,4\}$ thành $\{1,4\}$ và $\{2,3\}$.

Tác giả bài toán: Neal Wu, 2012