C. Сережа и подпоследовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Сережи есть последовательность, состоящая из n целых положительных чисел, a1, a2, ..., an.

Сначала Сережа записал на клетчатом листке бумаги все различные непустые неубывающие подпоследовательности последовательности a. Потом для каждой из последовательностей, записанных на клетчатом листке, Сережа записал на линованном листке все последовательности, которые ее не превышают.

Последовательность целых положительных чисел x = x1, x2, ..., xr не превышает последовательность целых положительных чисел y = y1, y2, ..., yr, если выполняются неравенства: x1 ≤ y1, x2 ≤ y2, ..., xr ≤ yr.

Сейчас Сережа интересуется, сколько последовательностей записано на листке в линию. Помогите Сереже, найдите остаток от деления описанного количества на 1000000007 (109 + 7).

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 105). Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106).

Выходные данные

В единственную строку выведите остаток от деления ответа на задачу на число 1000000007 (109 + 7).

Примеры
Входные данные
1
42
Выходные данные
42
Входные данные
3
1 2 2
Выходные данные
13
Входные данные
5
1 2 3 4 5
Выходные данные
719