Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại.

Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng một trong hai dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên ~a~ có ~n~ phần tử, hãy đếm số dãy con của ~a~ là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên ~n~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le n)~.

Output

In ra số lượng dãy tăng kép là dãy con của ~a~, sau khi chia lấy dư cho ~10^9+7~.

Scoring

Sample Input 1

4
3 3 4 2

Sample Output 1

9

Notes

Có ~9~ dãy con của dãy đã cho là dãy tăng kép: ~(3, 3)~, ~(3, 4)~, ~(3, 3, 4)~, ~(3, 4, 2)~, ~(3,2)~, ~(3, 4)~, ~(3, 2)~, ~(3, 4, 2)~, ~(4, 2)~.