K. Суммы и произведения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$. Подотрезком $$$a$$$ назовём массив, который можно получить удалением неотрицательного числа элементов из начала $$$a$$$ и удалением неотрицательного числа элементов из конца $$$a$$$.

Возьмём массив $$$b$$$ — подотрезок $$$a$$$. Рассмотрим все элементы, которые встречаются в массиве $$$b$$$ ровно $$$1$$$ раз. Посчитаем для каждого такого элемента $$$x$$$ произведение всех элементов массива слева от $$$x$$$, а также произведение всех элементов массива справа от $$$x$$$. При этом $$$x$$$ входит в оба этих произведения.

Назовём сплитом элемента сумму этих двух произведений. Наконец, назовём счётом подотрезка $$$b$$$ сумму сплитов для всех элементов, которые встречаются ровно $$$1$$$ раз. Ваша задача — найти сумму счётов всех подотрезков $$$a$$$.

Так как это число может быть очень большим, выведите его по модулю $$$10^9 + 7$$$.

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

В первой строке вводится единственное число $$$n$$$ $$$(1 \le n \le 10^5)$$$.

Во второй строке вводится $$$n$$$ чисел — массив $$$a$$$ $$$(1 \le a_i \le 10^9)$$$.

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

Выведите единственное число — ответ на задачу по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
3
1 1 2
Выходные данные
19
Входные данные
10
10 10 7 9 8 3 3 10 7 3
Выходные данные
1903656
Примечание

В первом примере существуют следующие подмассивы:

  • $$$[1]$$$: счёт $$$2$$$
  • $$$[1]$$$: счёт $$$2$$$
  • $$$[2]$$$: счёт $$$4$$$
  • $$$[1, 1]$$$: счёт $$$0$$$
  • $$$[1, 2]$$$: счёт $$$7$$$
  • $$$[1, 1, 2]$$$: счёт $$$4$$$