Một công ty muốn phân tích dữ liệu về mức tăng trưởng doanh số theo ngày. Trong \(n\) ngày liên tiếp, họ ghi nhận doanh số bán hàng mỗi ngày là một số nguyên \(x_1,x_2,…,x_n\).

Yêu cầu: Công ty muốn biết: Có bao nhiêu cách chọn ra một số ngày (theo thứ tự thời gian tăng dần) sao cho doanh số trong các ngày đó tăng dần? Nếu có hai cách chọn có cùng giá trị doanh số nhưng thuộc các vị trí khác nhau trong danh sách ngày, thì vẫn được tính là hai cách riêng biệt. Vì số lượng có thể rất lớn, hãy in ra kết quả modulo \(10^9+7\).

Ràng buộc:

• Subtask 1: 40% với \(n≤20;\)

• Subtask 2: 30% với\( n≤5000;\)

• Subtask 3: 30% với \(n≤2.10^5.\)

Dữ liệu

• Dòng 1: Chứa số nguyên dương\( n\), tương ứng là số ngày theo dõi.

• Dòng 2: Chứa \(n\) số nguyên \(x_1,x_2,…,x_n\) tương ứng là doanh số từng ngày.

Kết quả

• Một số nguyên là số lượng tập con các ngày có doanh số tăng dần, modulo\( 10^9+7.\)

Sample Input

4
5 1 2 3

Sample Output

8