THỰC HÀNH

Phú ông gần đất xa trời

Gọi 3 con lại ngỏ lời thiết tha

Rằng ruộng đất ông cha ta để lại

Các con đừng khờ dại bán đi

N thửa ruộng ngoài kia

Giữ nguyên diện tích, chia đều 3 con

Phú ông có N thửa ruộng có diện tích lần lượt là s₁, s₂, …, s_N. Em hãy giúp phú ông đếm xem có bao nhiêu cách chia hết các thửa ruộng cho 3 người con, mỗi người nhận một số thửa ruộng sao cho tổng diện tích của mỗi người con là như nhau và phải giữ nguyên diện tích các thửa ruộng.

Dữ liệu vào:

• Dòng chứa số nguyên dương N là số thửa ruộng.
• Dòng thứ hai chứa N số nguyên dương s₁, s₂, …, s_N, hai số liên tiếp cách nhau một dấu cách.

Dữ liệu ra:

Gồm một số nguyên là số cách chia, nếu không thể chia được thi ghi ra số -1.

Ví dụ:

Dữ liệu vào:
5
100 200 250 50 300

Dữ liệu ra:
6

Giải thích: Nếu gọi A, B, C là tên của 3 người con thì ta có 6 cách chia như sau: AABBC, AACCB, BBAAC, BBCCA, CCAAB, CCBBA.

Giới hạn: Trong tất cả các test: 1 ≤ N ≤ 20, 1 ≤ s_i ≤ 500

• 40% số test (ứng với 40% số điểm của bài) 1 ≤ N ≤ 10
• 30% số test (ứng với 30% số điểm của bài) 10 < N ≤ 15
• 30% số test (ứng với 30% số điểm của bài) 15 < N ≤ 20.