Pairwise Product

You are given an array of integers $a_1,a_2,\dots ,a_n$. Your task is to answer queries of the following type:

• For given $l,r$, output the sum of products for all pairs $l\le i<j\le r$. Formally, you need to compute $\sum _{l\le i<j\le r}{a}_i\cdot a_j$. The answer may be large, so output it modulo $10^9+7$.

Input

The first line contains a single number $n$ ($2\le n\le 2\cdot 10^5$) — the size of the array $a$.

The second line contains $n$ integers $a_1,\dots ,a_n$ $(1\le a_i\le 10^9)$ — the elements of the array.

The third line contains a single integer $q$ ($1\le q\le 2\cdot 10^5$) — the number of queries.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1\le l<r\le n$).

Output

Output $q$ lines — the answer to each query.

Examples

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Please note that the evaluation is still in the testing phase.

1. ($29$ points): $n\le 100$, $q\le 100$;

2. ($36$ points): $n\le 10000$, $q\le 100$;

3. ($35$ points): without additional constraints.