Bessie và Canmu tìm được một bao tải có ~N (1≤N≤250)~ đồng tiền vàng và chúng quyết định sẽ chia số tiền này thành hai phần đều nhất có thể. Đồng tiền thứ ~i~ có giá trị ~V_i (1≤V_i≤2000)~. Hai con bò sẽ cố gắng chia thành hai phần với tổng giá trị trong mỗi phần bằng nhau. Nếu như không thể làm được điều này chúng sẽ chia thành hai phần sao cho chênh lệch giữa phần lớn với phần nhỏ là nhỏ nhất có thể.

Bessie và Canmu nhận thấy rằng có thể có nhiều cách để làm điều trên và chúng muốn đếm xem có bao nhiêu cách chia các đồng tiền thành hai phần với sự chênh lệch giá trị là nhỏ nhất. Chú ý rằng trong trường hợp không phân chia được đều nhau thì Bessie luôn được chia phần lớn hơn.

Ví dụ, giả sử có ~5~ đồng tiền với mệnh giá ~2, 1, 8, 4~ và ~16~. Bessie và Cnmuu sẽ chia thành hai phần: phần của Bessie có ~1~ đồng trị giá ~16~ và phần của Canmu là các đồng tiền còn lại với giá trị ~2+1+8+4=15~ và chênh lệch giữa hai phần là ~16-15=1~. Ngoài ra đây là cách chia duy nhất nên chỉ có ~1~ cách chia như vậy.

Chú ý rằng những đồng tiền có cùng giá trị sẽ làm cho số cách chia tăng lên nhanh chóng. Ví dụ như với tập hợp ~(1,1,1,1)~ sẽ có ~6~ cách chia thành hai phần bằng nhau.

Input

• Dòng đầu tiên ghi số nguyên dương ~N~

• ~N~ dòng tiếp theo, dòng thứ ~i~ ghi số ~V_i~

Output

• Dòng ~1~ ghi chênh lệch nhỏ nhất giữa phần lớn và phần nhỏ

• Dòng ~2~ ghi số cách chia tìm được. Giá trị này có thể rất lớn nên chỉ cần in phần dư của nó khi chia cho ~10^6~.

Sample Input

5
2
1
8
4
16

Sample Output

1
1