Попарний добуток

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

• для заданих $l,r$ вивести суму добутків по всіх парах $l\le i<j\le r$. Формально, потрібно обчислити $\sum _{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\le 100$;

2. ($36$ балів): $n\le 10000$, $q\le 100$;

3. ($35$ балів): без додаткових обмежень.