Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tính số dãy con tăng khác nhau của mảng. Hai dãy con tăng chứa các giá trị giống nhau nhưng ở các vị trí khác nhau cũng được coi là hai dãy khác nhau.

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \leq n \leq 2\cdot10^5\)) - kích cỡ của mảng
• Dòng tiếp theo gồm \(n\) số nguyên \(x_1,x_2,...,x_n\) (\(1 \leq x_i \leq 10^9\)) mô tả mảng

Output

• In ra số dãy con tăng khác nhau theo modulo \(10^9+7\)

Example

3
2 1 3

5