\begin{problem}{Попарний добуток}{standard input}{standard output}{3 seconds}{256 megabytes}

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

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

\InputFile
Перший рядок містить одне число $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$).

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

\Scoring

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

\begin{enumerate}
\item ($29$ балів): $n\le 100$, $q\le100$;
\item ($36$ балів): $n\le 10\,000$, $q\le 100$;
\item ($35$ балів): без додаткових обмежень.
\end{enumerate}

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\exmpfile{example.03}{example.03.a}%
\end{example}

\end{problem}

