Дана неспадна послідовність. Визначити кількість зростаючих підпослідовностей даної послідовності.

Формат вхідних даних

У першому рядку дано одне число \(n\) ( \(1 ≤ n ≤ 5000\) ) — кількість елементів у послідовності.

У другому рядку дано самі елементи послідовності — натуральні числа, що не перевищують \(10^9\) .

Формат вихідних даних

Виведіть одне число — відповідь на завдання за модулем \(10^9 +7\) .

Примітка

У прикладі такі підпослідовності зростаючі: (1), дві підпослідовності (2) і дві підпослідовності (1, 2).

Приклад вхідних даних

3
1 2 2

Приклад вихідних даних

5