Hai xe chở rau

Một người nông dân có \(N\) luống rau, luống thứ \(i\) cho thu hoạch \(a_i\) gam. Ông muốn chọn một tập luống giao cho xe A và một tập luống khác giao cho xe B sao cho:

• Mỗi tập gồm ít nhất một luống, hai tập không có luống chung;
• Tổng lượng rau của hai xe bằng nhau.

Hãy đếm số cách chọn cặp \((\text{tập cho xe A}, \text{tập cho xe B})\). Cặp có thứ tự: đổi vai trò hai xe cho nhau được tính là một cách khác.

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• In ra số cách chọn.

Constraints

• \(1 \le N \le 22\)
• \(1 \le a_i \le 10^8\)

Sample Input 1

5
2 3 5 1 4

Sample Output 1

14

Sample Input 2

2
7 7

Sample Output 2

2

Explanation

Ở ví dụ 2 có hai cách: luống 1 cho xe A và luống 2 cho xe B, hoặc ngược lại.