Background

Problem provider: Okami.

Asada Shino: A good long-necked deer can count the number of digits in numbers.

Problem 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