Скільки зростаючих?

Нехай задано числову послідовність, що складається з N цілих чисел.

Потрібно визначити кількість строго зростаючих підпослідовностей у цій послідовності. Відповідь слід подати за модулем 1000007.

Вхідні дані

У першому рядку вхідного файлу задано число N. У наступному рядку наведено N цілих чисел, розділених одним або кількома пробілами, які є членами заданої послідовності (0 < N ≤ 11000, значення членів послідовності за модулем не перевищують 10^5).

Вихідні дані

В єдиному рядку виведіть відповідь на задачу.

Приклади