Cho một cân hai đĩa và \(n\) quả cân có khối lượng đôi một khác nhau \(w_1, w_2, . . , w_n\). Tiến hành đặt lần
lượt từng quả cân lên một trong hai đĩa của cân và đảm bảo rằng tổng khối lượng bên trái luôn nhỏ
hơn hoặc bằng tổng khối lượng bên phải.

Yêu cầu: Cho \(n\) quả cân có khối lượng \(w_1, w_2, . . , w_n\), hãy đếm số cách xếp \(n\) quả cân thỏa mãn.

Hai cách được gọi là khác nhau nếu thứ tự xếp các quả cân khác nhau hoặc tồn tại một quả cân nằm
ở đĩa khác nhau.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng 1: chứa số nguyên \(n\);
• Dòng 2: chứa \(n\) số nguyên dương \(w_1, w_2, . . , w_n\).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số cách xếp \(n\) quả cân lên đĩa.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 7\) và \(w_i \le 1000 (1 \le i \le n)\);
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 14\) và \(w_i \le 1000 (1 \le i \le n)\);
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 28\) và \(w_i = 2^{i−1} (1 \le i \le n)\).

Example

2
1 2

3

3
10 11 12

15