Sereja và các dãy con

Cho dãy số nguyên dương $a_1,a_2,\dots ,a_n$.

Xét tất cả các dãy con không giảm phân biệt của $a$. Với mỗi dãy con $y=(y_1,y_2,\dots ,y_r)$ thu được, đếm số dãy số nguyên dương $x=(x_1,x_2,\dots ,x_r)$ cùng độ dài thỏa mãn $x_1\le y_1$, $x_2\le y_2$, $\dots$, $x_r\le y_r$.

Hãy tính tổng số lượng dãy $x$ đếm được trên tất cả các dãy con không giảm phân biệt của $a$. Vì kết quả có thể rất lớn, hãy in ra theo modulo ${10}^9+7$.

Hai dãy con được coi là phân biệt nếu chúng khác nhau khi so sánh theo giá trị (không tính vị trí xuất hiện trong $a$). Ví dụ, với dãy $a=(1,2,2)$, hai dãy con không giảm phân biệt chứa cả hai giá trị $1$ và $2$ chỉ được tính một lần là $(1,2)$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất là đáp án theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^6$

Ví dụ