| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 5 | 5 | 1 | 100.000% |
Шерлок Холмс --- мастер решения любых головоломок, но не все тайны ему удается раскрыть сразу. Полгода назад связной принес ему письмо, зашифрованное некоторым шифром, но ключа, необходимого для расшифровки, в письме не было. Наметанный глаз детектива обратил внимание на необычайно длинный обратный адрес: вместо улицы и номера дома отправителя на конверте были написаны $n$ чисел. Как только ни пытался детектив прочитать письмо, все усилия были напрасны.
Проснувшись сегодня утром, Шерлок обнаружил у дверей своего дома детектива Лестрейда. Он принес свежую новость: Скотланд-Ярд поймал участника группировки таинственного профессора М., и тот согласился рассказать секрет шифра, используемого в их преступной сети, в обмен на смягчение приговора. Как и все гениальное, шифр оказался очень простым. Ключом к шифру является число, равное сумме по всем подотрезкам количества различных подпоследовательностей, которые можно составить, используя только числа из этого подотрезка.
Под подотрезком последовательности чисел длиной $n$ Шерлок понимает два числа $l, r,ドル такие, что 1ドル \le l \le r \le n,ドル и обозначает его $[l, r]$. Под подпоследовательностью подотрезка $[l, r]$ он понимает набор чисел $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ (возможно, пустой), для которого выполнено условие $l \le i_1 < i_2 < \ldots < i_k \le r$. Две подпоследовательности $a_i$ и $a_j$ считаются различными, если они имеют разную длину, или существует такое $k,ドル что $a_{i_k} \ne a_{j_k}$.
Поскольку это число может быть слишком большим, нужно взять его остаток от деления на число 1ドル,000円,000円,007円$. К сожалению, детектив не силен в математике, и ему нужна Ваша помощь в поиске ключа к шифру.
В первой строке входного файла дано одно целое число $n$ (1ドル \le n \le 100,000円$) --- количество чисел в последовательности.
Во второй строке входного файла даны $n$ целых чисел $a_i$ (1ドル \le a_i \le 100,000円$) --- элементы последовательности.
В единственной строке выходного файла выведите искомое число --- ключ к шифру по модулю 1ドル,000円,000円,007円$.
3 1 1 2
19
6 1 2 2 3 1 2
185
Пояснение к первому тестовому примеру:
Если есть набор чисел \{1, 1, 2\}, то есть шесть способов выбрать подотрезок в этом наборе:
1\} (2 подпоследовательности --- \{\}, \{1\}), 1\} (2 подпоследовательности --- \{\}, \{1\}), 2\} (2 подпоследовательности --- \{\}, \{2\}),1, 1\} (3 подпоследовательности --- \{\}, \{1\}, \{1, 1\}), 1, 2\} (4 подпоследовательности --- \{\}, \{1\}, \{2\}, \{1, 2\}), 1, 1, 2\} (6 подпоследовательностей --- \{\}, \{1\}, \{2\}, \{1, 1\}, \{1, 2\}, \{1, 1, 2\}). Таким образом, ответ равен 2ドル+2+2+3+4+6=19$.