Đếm dãy tăng dài nhất

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\). Một dãy con tăng là dãy gồm các phần tử được giữ lại từ \(A\) (theo đúng thứ tự ban đầu, không nhất thiết liền kề) sao cho các giá trị tăng ngặt từ trái sang phải. Trong tất cả các dãy con tăng, những dãy có độ dài lớn nhất gọi là dãy con tăng dài nhất.

Hãy đếm có bao nhiêu dãy con tăng dài nhất. Hai dãy con được coi là khác nhau nếu tập vị trí được chọn khác nhau (dù giá trị có thể trùng nhau). Vì đáp án có thể rất lớn, in ra kết quả sau khi chia dư cho \(10^9 + 7\).

Input

• Dòng đầu chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Output

In ra một số nguyên là số dãy con tăng dài nhất, lấy dư cho \(1000000007\).

Constraints

• \(1 \le N \le 5000\)
• \(|A_i| \le 10^9\)

Sample Input 1

6
2 1 3 2 4 3

Sample Output 1

4

Sample Input 2

5
4 4 4 4 4

Sample Output 2

5

Explanation

• Ví dụ 1: độ dài dài nhất là \(3\), có \(4\) dãy: \((2,3,4)\), \((1,3,4)\), \((1,2,4)\) và \((1,2,3)\).
• Ví dụ 2: độ dài dài nhất là \(1\), mỗi vị trí tạo một dãy riêng nên có \(5\) dãy.