Bessie và Canmuu tìm thấy túi $N$ đồng vàng ($1 \leq N \leq 250$) muốn chia đều nhất có thể. Đồng $i$ có giá trị $v_i$ ($1 \leq V_i \leq 2{,}000$). Hai bò muốn hai đống bằng nhau nhưng không phải luôn làm được. Chênh lệch giá trị nhỏ nhất là bao nhiêu?

Có thể có nhiều cách đạt chênh lệch nhỏ nhất. Họ cũng muốn biết số cách chia công bằng nhất. Nếu không thể chia đều, Bessie nhận đống giá trị lớn hơn.

Ví dụ năm đồng có giá trị $2, 1, 8, 4, 16$. Một đống chỉ có đồng $16$, đống kia có phần còn lại giá trị $1+2+4+8=15$. Chênh lệch $16-15 = 1$. Chỉ có một cách như vậy nên số cách chia đều nhất là $1$.

Đổi các đồng cùng giá trị giữa hai đống làm tăng số cách tối ưu. Vì thế $\{1, 1, 1, 1\}$ có sáu cách tối ưu khác nhau, mỗi đống hai đồng.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

• Dòng $1$: một số nguyên $N$.

• Các dòng $2..N+1$: dòng $i+1$ chứa một số nguyên $V_i$.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

• Dòng $1$: một số nguyên là chênh lệch giá trị nhỏ nhất giữa hai đống.

• Dòng $2$: số cách chia với chênh lệch nhỏ nhất ở dòng đầu. Số này có thể lớn; in phần dư khi chia cho $1,000,000$.

Ví dụ

Dữ liệu vào 1

5
2
1
8
4
16

Dữ liệu ra 1

1
1

Nguồn bài toán: Sherry Wu, bài kinh điển, 2010