Didn't I Say to Make My Abilities Average in the Next Life?!

When reincarnating in the fantasy world, Kurihara asked the Creator to grant her the ability to average. But the Creator does really badly on math, so he considers "average" as half of the sum of the maximum and minimum among values.

There're $n$ kinds of creatures in the fantasy world, numbered from $1$ to $n$. Each creature has an ability value. The ability value of the $i$-th kind of creature is $a_i$. The Creator has $m$ schemas of granting ability. For the $i$-th schema, The Creator will choose an interval $[l,r]\ (x\le l\le r\le y)$ from a certain interval $[x,y]\ (1\le x\le y\le n)$ in a uniformly random way, calculate the "average" of the ability value from the $l$-th creature to the $r$-th creature in his own definition, and grant it to Kurihara. Please note that the definition of "average" here is half the sum of the maximum and minimum among values.

Kurihara would like to know the mathematical expectation of the ability value she will be granted.

The first line of input contains one integer $T\ (1\le T\le 10)$, indicating the number of test cases.

For each test case, the first line contains two integers $n,m\ (1\le n, m\le 2\times 10^5)$, indicating the number of creatures and the number of schemas of granting ability, respectively.

The second line contains $n$ integers $a_1,a_2,\ldots ,a_n\ (1\le a_i\le 10^9)$, indicating the ability value of each creature.

For the next $m$ lines, the $i\ (1\le i\le m)$-th line contains two integers $x,y\ (1\le x\le y\le n)$, indicating the $i$-th schema.

It is promised that for all test cases, $\sum n\le 3\times 10^5,\sum m\le 3\times 10^5$.

For each test case, output $m$ lines. On the $i$-th line, output the answer to the $i$-th schema in the fraction form modulo $10^9+7$ in one line. That is, if the answer is $\frac{P}{Q}$, you should output $P\cdot Q^{-1}\bmod (10^9+7)$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $10^9+7$.

1
6 4
1 1 4 5 1 4
1 1
4 5
1 4
1 6

1
3
750000008
809523818

2021“MINIEYE杯”中国大学生算法设计超级联赛（4）