Cho một cân hai đĩa và n quả cân có khối lượng đôi một khác nhau w₁, w₂, ... 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₁, w₂, ... w_n, hãy đếm số cách xếp quả n 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

- Dòng đầu chứa số nguyên ;
- n dòng sau, dòng thứ i chứa một số nguyên w_i là khối lượng của cân thứ i.

Output

- Gồm một dòng chứa một số nguyên là số cách xếp n quả cân lên đĩa.