Description

The giraffe Abbi likes to roll its face on the keyboard. Each time it does so, it multiplies the values in some sub-interval.

A sub-interval is a contiguous interval within an interval.

The weight of a sub-interval is defined as the product of the weights of all its elements.

The expected weight of an interval is defined as the expected value of the weight of a sub-interval chosen uniformly at random from all sub-intervals of that interval.

Given $n$ numbers, where the $i$-th number is the weight $a_i$.

There are $q$ queries. For each query $l \ \ r$, ask for the expected weight of the specified interval.

Input Format

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers, the $i$-th integer is the initial value $a_i$ of the sequence.

The next $q$ lines each contain two integers $l \ \ r$, representing the query interval.

Output Format

For each query, output the expected weight of the specified interval.

Since the expected weight can be very large, output the expected weight modulo $100000007$.

Do not ask what to do if it is not divisible; see above.

If it still does not work, please refer to https://www.luogu.org/problem/P2613.

5 3
6 12 6 3 27
1 1
4 5
1 3

6
37
100

Hint

Time and memory limits: 1 s / 512 MB.

For $30\%$ of the testdata, $1 \leq n, q \leq 100$.

For $100\%$ of the testdata, $1 \leq n, q \leq 10^6$, $1 \leq a_i \leq 10^7$.

Sample explanation: For the interval $[1,1]$, there is only one sub-interval $[1,1]$ with weight $6$. The probability of choosing each sub-interval is $\frac{1}{1}$, so the expected weight is 6.

For the interval $[4,5]$, there are three sub-intervals $[4,4]$, $[4,5]$, and $[5,5]$, with weights $3$, $81$, and $27$ respectively. The probability of choosing each sub-interval is $\frac{1}{3}$, so the total expected weight is $37$.

For the interval $[1,3]$, there are six sub-intervals $[1,1]$, $[1,2]$, $[1,3]$, $[2,2]$, $[2,3]$, and $[3,3]$, with weights $6$, $72$, $432$, $12$, $72$, and $6$ respectively. The probability of choosing each sub-interval is $\frac{1}{6}$, so the total expected weight is $100$.

It is recommended to use fast input.

Translated by ChatGPT 5