Sau khi đã vượt qua thử thách trước đó của Cheow một cách xuất sắc, Beo ngày càng tự tin vào khả năng của mình. Tuy nhiên, Talulu, người được mệnh danh là - Trí tuệ tối thượng của học viện Toán Thuật, đã đưa ra một bài toán nâng cấp khó hơn để thử thách Beo:

Cho một dãy số nguyên gồm ~N~ phần tử. Nhiệm vụ của bạn là tìm ra số lượng dãy con tăng dần nghiêm ngặt có độ dài lớn nhất, sao cho tổng số dãy con được đếm là ít nhất có thể.

Cụ thể:

• Một dãy con tăng dần nghiêm ngặt là dãy con (không nhất thiết liên tiếp) ~A_{i_1}, A_{i_2}, ..., A_{i_k}~ với ~i_1 < i_2 < ... < i_k~ và ~A_{i_1} < A_{i_2} < ... < A_{i_k}~.
• Bạn chỉ cần đếm số lượng dãy con có độ dài bằng với độ dài lớn nhất có thể.
• Vì số lượng dãy con có thể rất lớn, hãy in ra kết quả chia dư cho ~10^9 + 7~.

Input

• Dòng đầu tiên là một số nguyên dương ~N~ ~(1 ≤ N ≤ 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^{9})~.

Output

• Một số nguyên là số lượng dãy con tăng nghiêm ngặt dài nhất, ~modulo~ ~10^9 + 7~.

📌 Example

Input

4
2 3 5 4 

Output

2

💡 Explanation

• Các dãy tăng dần dài nhất có độ dài là 3.

• Có đúng 2 dãy như vậy:

  • 2 3 5
  • 2 3 4