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

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

1 секунда

64 мегабайти

Дуже легка

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

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

Вхідні дані

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

Вихідні дані

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

Приклади

Приклад 1