Hùng đang có một dãy số nguyên dương, mỗi thao tác có thể chọn hai số kề nhau trên dãy và thay hai số đó bằng tổng của chúng. Hùng muốn thực hiện một dãy các thao tác như vậy (có thể thực hiện \(0\) thao tác) để thu được một dãy không giảm. Hùng muốn đếm xem có bao nhiêu dãy khác nhau có thể nhận được.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) - số phần tử của dãy \((n \leq 7000)\).
• Dòng tiếp theo chứa \(n\) số nguyên: \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\).

Output

• Gồm duy nhất một số nguyên là kết quả của bài toán chia lấy dư cho \(10^9+7\).

Scoring

• \(20\%\) số điểm thỏa mãn \(n \leq 20\),
• \(30\%\) số điểm khác thỏa mãn \(n \leq 500\),
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.

Example

5
2 1 3 3 1

5

Các dãy có thể tạo ra là {10}, {3, 7}, {3, 3, 4}, {2, 8}, {2, 4, 4}

Nguồn: Phạm Bá Thái