Попарний добуток
ліміт часу на тест
3 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Вам задано масив цілих чисел $$$a_1,a_2,\dots,a_n$$$. Ваша задача — відповісти на запити наступного типу:

- для заданих $$$l,r$$$ вивести суму добутків по всіх парах $$$l\le i<j\le r$$$. Формально, потрібно обчислити $$$\sum\limits_{l\le i<j\le r}a_i\cdot a_j$$$. Відповідь може бути завеликою, тому виведіть її по модулю $$$10^9+7$$$.

Вхідні дані

Перший рядок містить одне число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — розмір масиву $$$a$$$.

Другий рядок містить $$$n$$$ цілих чисел $$$a_1,\dots,a_n$$$ $$$(1\le a_i\le 10^9)$$$ — елементи масиву.

Третій рядок містить одне ціле $$$q$$$ ($$$1\le q\le 2\cdot 10^5$$$) — кількість запитів.

Кожен з наступних $$$q$$$ рядків містить по два цілі числа $$$l$$$ та $$$r$$$ ($$$1\le l<r\le n$$$).

Вихідні дані

Виведіть $$$q$$$ рядків — відповідь до кожного запиту.

Система оцінки

У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.

1. ($$$29$$$ балів): $$$n\le 100$$$, $$$q\le100$$$;
2. ($$$36$$$ балів): $$$n\le 10\,000$$$, $$$q\le 100$$$;
3. ($$$35$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані

    21 211 2

Вихідні дані

    2

Вхідні дані

    52 3 4 5 661 43 51 52 34 52 5

Вихідні дані

    71
    74
    155
    12
    30
    119

Вхідні дані

    5100 10000 100000 1000000 1000000011 5

Вихідні дані

    110921516