Chia ruộng

Trong làng Omega có một ông phú hộ rất giàu có. Tài sản của ông rất nhiều trâu, bò, và cả... ruộng vườn. Một hôm ông gọi 3 người con đã đến tuổi trưởng thành đến, và định chia cho mỗi người một phần ruộng để làm ăn.

Ông có tổng cộng \(n\) thửa ruộng, mỗi thửa có diện tích nguyên dương. Ông muốn chia đều toàn bộ \(n\) thửa ruộng này cho 3 người con, sao cho:

• Mỗi người nhận một nhóm thửa ruộng (có thể không bằng nhau về số lượng).
• Tổng diện tích của ruộng mỗi người nhận phải bằng nhau.

Hỏi có bao nhiêu cách chia \(n\) thửa ruộng đó thành 3 phần sao cho thỏa điều kiện trên?

Chú ý: Hai cách chia được coi là khác nhau nếu có ít nhất một thửa ruộng được phân cho người khác.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \le n \le 20)\) --- số thửa ruộng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((100 \le a_i \le 5000)\) --- diện tích của từng thửa ruộng.

Output

In ra một số nguyên là số cách chia hợp lệ. Nếu không thể chia được, in ra -1.

Example

5
100 200 250 50 30

-1