Рабочее место участника

Имеется массив `a` из `n` натуральных чисел. Необходимо для заданной части массива с i-го до j-го элемента подсчитать сумму `(sum_{forall\ v\ in\ a_i…a_j\ }\ v^{"count"(v)})\ mod\ (10^9+7)`, где `"count"(v)` – сколько раз `v` встречается среди элементов `a_i…a_j`.

Первая строка ввода содержит два целых числа – длину массива `n` и количество запросов `m` (`1\ ≤\ n,\ m\ ≤\ 300000`). Вторая строка содержит `n` целых чисел в диапазоне от 1 до 100000 – массив чисел. Следующие `m` строк содержат по два целых числа `l_j` и `r_j` (`1\ ≤\ l_j\ ≤\ r_j\ ≤\ n`) – запросы на получение суммы для элементов массива с `l_j`-го по `r_j`-й.

Для каждого запроса вывести в отдельной строке подсчитанную сумму.

5 3
3 3 3 3 5
1 5
3 3
3 5

86
3
14