Giải bài trực tuyến

Cho dãy số a₁,a₂,a₃,...,a_n. Hãy đếm số lượng dãy con tăng dài nhất của dãy số trên.

Một dãy con độ dài k của dãy a được xác định bởi một bộ chỉ số (u₁≤u₂≤u₃≤...≤u_k) (1≤u_i≤n). Hai dãy con (u₁,u₂,u₃,...,u_k) và  (v₁,v₂,v₃,...,v_t) được gọi là khác nhau nếu k≠t hoặc tồn tại một vị trí i sao cho u_i≠v_i.

Input

• Dòng đầu tiên ghi số nguyên dương n (n≤10⁵)
• Dòng tiếp theo ghi n số nguyên mô tả dãy a (a_i≤10⁹)

Output

• Một dòng duy nhất ghi kết quả theo module 1000000007

Example

Input:
6
1 1 2 2 3 3
Output:
8