Tổ chức $C$ là một tổ chức lớn, với $n$ đơn vị trực thuộc ($n>=3$), đơn vị $i$ có $a_i$ người ($1\le a_i\le{10}^3$). Sắp tới, tổ chức $C$ cần chọn ra $n-2$ đơn vị để tham gia một sự kiện nội bộ $H$, với yêu cầu:

• Tất cả mọi người trong $n-2$ đơn vị này đều tham gia $H$.
• Tất cả mọi người tham gia $H$ đều trong $n-2$ đơn vị này.
• $H$ có một số hoạt động theo cặp, do đó số người tham gia $H$ phải chia hết cho 2.

Yêu cầu

Hãy giúp tổ chức $C$ tính xem có bao nhiêu cách lựa chọn khác nhau đảm bảo được yêu cầu trên. Hai cách lựa chọn được coi là khác nhau nếu có ít nhất 1 đơn vị được lựa chọn trong cách này nhưng không được lựa chọn trong cách kia.

Dữ liệu

Vào từ đầu vào chuẩn

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Kết quả

Ghi ra đầu ra chuẩn 1 số nguyên là số cách khác nhau để lựa chọn $n-2$ đơn vị sao cho yêu cầu được đảm bảo.

Ví dụ mẫu

5
3 4 5 7 12	

6

Giới hạn

Subtask 1 (20% số điểm): $n\le{10}^4$.

Subtask 2 (80% số điểm): $n\le{10}^6$.