Farmer John sở hữu \(N\) con bò (\(2 \le N \le 20\)), trong đó mỗi ngày con bò \(i\) cho \(M(i)\) đơn vị sữa (\(1 \le M(i) \le 100\,000\,000\)). FJ muốn tinh giản công việc vắt sữa đàn bò hằng ngày nên lắp đặt một máy vắt sữa hoàn toàn mới trong chuồng. Thật không may, chiếc máy này lại quá nhạy: nó chỉ hoạt động đúng nếu những con bò ở phía bên trái chuồng có tổng sản lượng sữa chính xác bằng tổng sản lượng sữa của những con bò ở phía bên phải chuồng!

Ta gọi một tập con của đàn bò là "cân bằng" nếu có thể chia nó thành hai nhóm có tổng sản lượng sữa bằng nhau. Vì chỉ một tập con cân bằng mới có thể làm máy vắt sữa hoạt động, FJ muốn biết có bao nhiêu tập con trong số \(N\) con bò của mình là cân bằng. Hãy giúp ông tính số lượng này.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa \(M(i)\).

Dữ liệu ra

• Dòng 1 chứa số tập con cân bằng của đàn bò.

Ví dụ

4
1
2
3
4

3

Nguồn

USACO 2012 US Open, Gold Division — Balanced Cow Subsets

Tác giả: Neal Wu, 2012.