Cho trước một mảng gồm \(n\) số nguyên, bạn cần tính số lượng dãy con tăng mà nó chứa. Nếu hai dãy con có các giá trị giống nhau nhưng ở những vị trí khác nhau trong mảng, chúng được tính là khác nhau.

Input

Dòng đầu tiên chứa số nguyên \(n:\) kích thước của mảng.

Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n:\) nội dung của mảng.

Output

In ra một số nguyên là số lượng dãy con tăng theo modulo \(10^9 + 7\).

Constraints

• \(1≤n≤2⋅10^5\)
• \(1≤x_i≤10^9\)

Example

Sample Input:

3
2 1 3

5

Note

Các dãy con tăng là \([2], [1], [3], [2,3]\) và \([1,3]\).