Дано масив з ~n~ цілих чисел. Ваше завдання полягає в тому, щоб обчислити кількість зростаючих підпослідовностей, які він містить.

Якщо дві підпослідовності мають однакові значення, але на різних позиціях у масиві, вони підраховуються окремо.

Обмеження

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le x_i \le 10^9~

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

Перший рядок містить ціле число ~n~: розмір масиву.

Другий рядок містить ~n~ цілих чисел ~x_1,x_2,\dots,x_n~: вміст масиву.

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

Виведіть одне ціле число: кількість зростаючих підпослідовностей за модулем ~10^9+7~.

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

3
2 1 3

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

5

Пояснення

Зростаючими підпослідовностями є [2], [1], [3], [2,3] і [1,3].