Орехус зачем-то нашел массив целых чисел \(a\) длины \(n\). Назовем подотрезком \(l \ldots r\) массива подпоследовательность подряд идущих элементов массива с \(l\) по \(r\), то есть \(a_l, a_{l+1}, a_{l+2}, \ldots, a_{r-1}, a_{r}\).
Никто не знает почему, но он считает пару подотрезков хорошими тогда и только тогда, когда выполняются следующие условия:
- Эти подотрезки не вложены, друг в друга. То есть, каждый подотрезок должен содержать элемент (со своим индексом), который не принадлежит другому.
- Подотрезки пересекаются и каждое число, принадлежащее пересечению отрезков (как элемент), принадлежит каждому их них ровно по одному разу.
Например \(a=[1, 2, 3, 5, 5]\). Пары отрезков \((1 \ldots 3; 2 \ldots 5)\) и \((1 \ldots 2; 2 \ldots 3)\) — хорошие, а \((1 \dots 3; 2 \ldots 3)\) и \((3 \ldots 4; 4 \ldots 5)\) — нет (отрезок \(2 \ldots 3\) вложен в \(1 \ldots 3\); число \(5\) встречается в обоих отрезках, но в отрезке \(4 \ldots 5\) встречается дважды.
Помогите Орехусу узнать количество пар хороших подотрезков! Так как ответ может быть очень большой выведите его по модулю \(10^9+7\).
Примечание
В первом примере есть только одна пара хороших подотрезков: \((1 \ldots 2, 2 \ldots 3)\).
Во втором примере есть четыре пары хороших подотрезков:
- \((1 \ldots 2, 2 \ldots 3)\)
- \((2 \ldots 3, 3 \ldots 4)\)
- \((2 \ldots 3, 3 \ldots 5)\)
- \((3 \ldots 4, 4 \ldots 5)\)