(Các điểm khác nhau giữa bài 2 và bài 3 là giới hạn \(n\), \(a[i]\) và số mod)

Canuc80k có \(3\) người con: Minh, Sam và Ngọc. Ông giành tình thương cho cả ba như nhau. Biết mình đã có tuổi, chẳng sống được lâu nữa. Trước lúc lâm chung, ông muốn chia gia tài cho những người con của mình. Tài sản của ông chẳng có gì ngoài vài mảnh đất hai mặt tiền bên quận 1 Sài Gòn. Đánh số các mảnh đất từ \(1\) đến \(n\), mảnh đất thứ \(i\) sẽ có diện tích là \(a_i\) \(\text{km}^2\). Khi chia gia tài, ông muốn sao cho Ngọc có nhiều diện tích đất nhất, còn hai người con trai sẽ được chia bằng nhau. Tính số cách chia khác nhau mà Canuc80k có thể thực hiện. \(2\) cách chia được coi là khác nhau khi tồn tại một mảnh ruộng \(i\) được chia cho người \(X\) ở cách thứ nhất nhưng chia cho người \(Y\) ở cách thứ \(2\) (\(X \neq Y\)).

Input

Vào từ file văn bản BAI2.INP:

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 19\))
• Dòng tiếp theo chứa các số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^{12}\))

Output

Ghi ra file văn bản BAI2.OUT:

• Kết quả bài toán

Ràng buộc

• \(25\%\) số lượng test \(n \le 15\)
• \(25\%\) số lượng test \(n \le 17\)
• \(30\%\) số lượng test \(n \le 18\)
• \(20\%\) số lượng test không giới hạn gì thêm

Example

3
100000000 1 1

3