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

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

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

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

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

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

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

В тесте из условия Михаил может найти следующие 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}.