Миллион алых роз

문제

Восьмое марта только началось, а перед входом в цветочный магазин «Аделина» уже выстроилась огромная очередь желающих приобрести букеты красивейших свежих алых роз. Хозяин магазина Александр понимал, что день сегодня предстоит нелегкий. Поэтому он решил предварительно узнать у каждого из ожидающих покупателей, сколько всего роз тот хотел бы приобрести. Полученные числа Александр аккуратно выписал на листок и понял, что в одиночку ему не справиться.

Чтобы ускорить процесс формирования букетов, хозяин магазина позвал на помощь своего коллегу Михаила. Александр показал ему полученный только что список и предложил выписать подпоследовательность размеров букетов, формированием которых Михаил готов заняться.

Михаила не интересует оптимальное распределение работы. Не интересуют его также максимальный, минимальный и даже средний размеры формируемых им букетов. Все, что он хочет знать, — количество различных непустых подпоследовательностей в списке Александра по модулю 10⁹ + 7.

입력

В первой строке вводится целое число N — количество ожидающих покупателей (1 ⩽ N ⩽ ⩽ 1 000 000). Вторая строка содержит N натуральных чисел, i-е из которых описывает, сколько роз желает купить i-й человек в очереди (1 ⩽ a_i ⩽ 1 000 000).

출력

Выведите ответ на вопрос, терзающий Михаила, — количество различных подпоследовательностей в составленном Александром списке по модулю 1 000 000 007 (10⁹ + 7).

힌트

Подпоследовательностью {x_nk} называется числовая последовательность, которая составлена из членов последовательности {x_n} и в которой порядок следования ее элементов совпадает с их порядком следования в исходной последовательности {x_n}.

В тесте из условия Михаил может найти следующие 13 различных подпоследовательностей: {1}, {1, 1}, {1, 1, 3}, {1, 2}, {1, 2, 1}, {1, 2, 1, 3}, {1, 2, 3}, {1, 3}, {2}, {2, 1}, {2, 1, 3}, {2, 3}, {3}.

4
1 2 1 3

13