Sơn muốn sử dụng các tấm gỗ có sẵn để ghép thành hàng rào xung quanh vườn. Hàng rào có dạng hình đa giác lồi (diện tích khác 0) được ghép từ các cạnh là các tấm gỗ đặt nằm ngang. Sơn không muốn cưa hay phá hỏng các tấm gỗ để làm hàng rào. Rõ ràng không phải từ các tấm gỗ bất kì nào cũng có thể ghép thành hàng rào đa giác lồi.

Ví dụ từ 3 tấm gỗ có độ dài 10,11,12 có thể ghép thành hàng rào tam giác, tuy nhiên từ 4 tấm gỗ có độ dài 100,1,2,3 thì không thể ghép thành hàng rào tứ giác vì tấm gỗ dài 100 lớn hơn tổng độ dài của 3 tấm gỗ còn lại.

Sơn có \(n\) tấm gỗ. Sơn tự hỏi có bao nhiêu cách chọn ra các tấm gỗ từ các tấm đã có để từ chúng có thể ghép thành hàng rào đa giác lồi. Hai cách chọn được gọi là khác nhau nếu như có một tấm gỗ thuộc cách chọn này nhưng không thuộc cách chọn kia.

Yêu cầu: Bạn hãy giúp Sơn trả lời câu hỏi này. Kết quả là số dư của số cách chọn trong phép chia cho \(10^9+7\).

Input:

• Dòng đầu tiên chứa số nguyên \(n (1 ≤ n ≤ 5000)\) là số lượng tấm gỗ.

• Dòng thứ hai chứa \(n\) số nguyên \(l_i (1 ≤ l_i ≤ 5000)\) là độ dài các tấm gỗ.

Output:

Ghi một dòng duy nhất là kết quả của bài toán.

Sample Input

5
1 2 3 4 6

Sample Output

7

Sample Input

4
5 5 5 5

Sample Output

5

Sample Input

5
10 1 2 3 50

Sample Output

0

Sample Input

6
12 16 14 8 17 7

Sample Output

40

Ràng buộc

• Subtask 1: \(n ≤ 40\)

• Subtask 2: \(n ≤ 500 \)

• Subtask 3: \(n ≤ 5000\)