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. Do số lượng cách chọn có thể rất lớn nên bạn cần đưa ra số dư của số cách chọn trong phép chia cho \(10^9 + 7\).

Input

Dữ liệu nhập vào từ file CPOLY.INP:

• Dòng đầu tiên chứa số nguyên \(n\) \(\left( 1 \le n \le 5000 \right)\) là số lượng tấm gỗ.
• Dòng thứ hai chứa \(n\) số nguyên \(l_i\) \(\left( 1 \le l_i \le n \right)\) là độ dài các tấm gỗ.

Output

Kết quả ghi vào file CPOLY.OUT một dòng duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 40\);
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 500\);
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 5000\).

Example