Số dãy con tăng cực đại

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 các phần tử giữ lại từ \(A\) theo đúng thứ tự ban đầu (không cần liền kề) sao cho giá trị tăng ngặt. Dãy con tăng có số phần tử nhiều nhất gọi là dãy con tăng dài nhất.

Hãy đếm số dãy con tăng dài nhất của \(A\). Hai dãy con là khác nhau nếu tập chỉ số được chọn khác nhau. In kết quả sau khi lấy 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, chia dư cho \(1000000007\).

Constraints

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

Sample Input 1

6
7 7 7 9 9 9

Sample Output 1

9

Sample Input 2

7
-3 5 -3 2 8 2 7

Sample Output 2

8

Explanation

• Ví dụ 1: độ dài lớn nhất là \(2\); chọn một số \(7\) (3 cách) và một số \(9\) (3 cách) nên có \(3 \cdot 3 = 9\) dãy.
• Ví dụ 2: độ dài lớn nhất là \(3\). Có \(2\) dãy dạng \((-3, 5, x)\) với \(x \in \{8, 7\}\), và \(6\) dãy dạng \((-3, 2, x)\) khi tính theo vị trí (hai vị trí cho số \(-3\), hai vị trí cho số \(2\), với điều kiện \(x\) đứng sau), tổng cộng \(8\) dãy.