Dãy con của một dãy là dãy thu được bằng cách xoá đi một số phần tử của dãy ban đầu (có thể không xoá 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ó 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 chứa 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 \(1000000007\).

Example

4
3 3 4 2

9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 200\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 2000\) và \(a_i \le 200\).
• Subtask \(4\) (\(35\%\) số điểm): \(n \le 2000\).