The collector Xiao Lan has $n$ gems, where the $i$-th gem has a brightness of $a_i$. Xiao Lan wants to divide these gems into several groups such that each gem is assigned to exactly one group.

For a group of gems with $k$ gems having brightnesses $b_1, b_2, \dots, b_k$, Xiao Lan defines the aesthetic value of this group as $\frac{(\sum_{i=1}^k b_i)^2}{k^2}$. For a grouping scheme, Xiao Lan defines its aesthetic value as the sum of the aesthetic values of all groups.

Xiao Lan has $q$ queries. Each query asks: if the number of gems in each group must be between $l$ and $r$ (inclusive), what is the maximum aesthetic value that can be achieved among all valid grouping schemes?

Since the answer may be a large fraction $\frac{a}{b}$, for ease of output, you only need to provide the result modulo $10^9 + 7$. That is, you need to find an integer $c$ in the range $[0, 10^9 + 7)$ such that $a \equiv bc \pmod{10^9 + 7}$. It can be proven that under the constraints of this problem, such a $c$ always exists and is unique. Specifically, if no valid grouping scheme exists, output $-1$.

Input

Read data from standard input.

The first line contains two positive integers $n, q$ ($1 \le n, q \le 5 \times 10^5$), representing the total number of gems and the number of queries.

The second line contains $n$ non-negative integers, where the $i$-th integer represents the brightness $a_i$ of the $i$-th gem ($0 \le a_i \le 10^8$).

The next $q$ lines each contain two positive integers $l, r$ ($1 \le l \le r \le n$), representing the query where the number of gems in each group must be between $l$ and $r$.

Output

Output to standard output.

Output $q$ lines, where the $i$-th line contains an integer representing the answer to the $i$-th query, which is the maximum aesthetic value achievable modulo $10^9 + 7$ given the constraints on the group size. Specifically, if no valid grouping scheme exists, output $-1$.

Examples

Input 1

6 4
13 9 7 5 6 10
1 5
4 6
2 3
4 4

Output 1

460
444444517
500000230
-1

Note

For the first query, the optimal grouping scheme is to assign each gem to a separate group, i.e., $\{13\}, \{9\}, \{7\}, \{5\}, \{6\}, \{10\}$, at which point the aesthetic value is $460$, which is the maximum.

For the second query, there is only one unique grouping scheme $\{13, 9, 7, 5, 6, 10\}$, where the aesthetic value reaches the maximum $\frac{625}{9}$, and the result modulo $10^9 + 7$ is $444444517$.

For the third query, the optimal grouping scheme is $\{13, 10\}, \{9, 7\}, \{5, 6\}$, where the aesthetic value reaches the maximum $\frac{453}{2}$, and the result modulo $10^9 + 7$ is $500000230$.

For the fourth query, the size of each group must be $4$, but the total number of gems $6$ is not a multiple of $4$, so there will always be some remaining gems that cannot be grouped. Therefore, no valid grouping scheme exists, and we output $-1$.