Bạn Lương có \(3\) em gái. Trong lúc nhàn rỗi, bạn Lương mua về một số gói trong \(n\) gói kẹo ở cửa hàng, gói kẹo thứ \(i\) chứa \(a[i]\) viên kẹo. Vì không muốn \(3\) em gái ghen tị nhau, Lương sẽ chia số kẹo sao cho không có em gái nào được nhận số kẹo lớn hơn hoặc bằng tổng số kẹo của \(2\) em còn lại. Một tập hợp các gói kẹo là thỏa mãn nếu có thể chia thành \(3\) phần khác rỗng, mỗi em gái nhận \(1\) phần mà vẫn đảm bảo điều kiện trên. Hỏi có bao nhiêu tập hợp gói kẹo thỏa mãn mà Lương có thể mua? Vì số tập hợp là rất lớn, nên bạn cần in kết quả khi chia lấy dư cho \(10^9 + 7\).

Input

• Dòng đầu tiên gồm 1 số nguyên dương \(n\) \((n \leq 1000)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\), là số kẹo trong gói kẹo thứ \(i\) \((a_i \leq 5000)\).

Output

• In ra số nguyên là đáp án cần tìm.

Scoring

• Subtask \(1\): \(\ n \leq 10, a[i] \leq 500\).
• Subtask \(2\): \(\ n \leq 15, a[i] \leq 500\).
• Subtask \(3\): \(\ n \leq 20, a[i] \leq 500\).
• Subtask \(4\): \(\ n \leq 100, a[i] \leq 500\).
• Subtask \(5\): \(\ n \leq 1000, a[i] \leq 5000\).

Example

4
2 5 1 4

2

5
3 8 6 3 10

11