Pairwise Product
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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\limits_{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.

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\le100$$$;
2. ($$$36$$$ points): $$$n\le 10\,000$$$, $$$q\le 100$$$;
3. ($$$35$$$ points): without additional constraints.

Examples

Input

    21 211 2

Output

    2

Input

    52 3 4 5 661 43 51 52 34 52 5

Output

    71
    74
    155
    12
    30
    119

Input

    5100 10000 100000 1000000 1000000011 5

Output

    110921516