F. Vacation II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ariel is going on a vacation to cities $$$0 \dots n$$$ again! The cities are arranged in a row, with city $$$0$$$ on the left and city $$$n$$$ on the right. The cities from $$$1 \dots n$$$ all have some kind of cereal, denoted by integer $$$a_i$$$. Currently, Ariel is in city $$$0$$$ (there's no cereal in city $$$0$$$).

Each day, if Ariel is in city $$$k$$$, he will randomly (not necessarily uniformly) fly to any city from $$$k + 1 \dots n$$$ in such a way that he is $$$\frac{a_i}{a_j}$$$ times as likely to visit city $$$i$$$ compared to city $$$j$$$. Then, he buys a box of cereal from the city he arrives at.

However, some cities may be at war with each other (for example, they might disagree on whether milk or cereal goes first). If Ariel flies between two cities at war with each other, he will be deported and sent back to city $$$0$$$, and all his cereal boxes will be taken away. You will answer $$$q$$$ queries of the following form: if all cities from $$$l$$$ to $$$r$$$ are at war with each other, what is the expected number of cereal boxes Ariel will have when he reaches city $$$n$$$ modulo $$$10^9+7$$$? It is guaranteed none of the queries will involve city $$$n$$$

Input

The problem has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases.

The first line of each test case contains two integers, $$$n$$$ and $$$q$$$ ($$$3 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 2 \cdot 10^5$$$). The next line contains $$$n$$$ integers, $$$a_1 \dots a_n$$$ ($$$1 \leq a_i \leq 5000$$$). $$$q$$$ lines follow, each containing two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \lt r \lt n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot10^5$$$, and the sum of $$$q$$$ over all test cases also doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print $$$q$$$ integers; the $$$i$$$th integer should be the answer to the $$$i$$$th query modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod M$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output an integer $$$x$$$ such that $$$0 \leq x \lt M$$$ and $$$x \cdot q \equiv p \pmod M$$$.

Example
Input
2
3 1
1 2 3
1 2
4 2
1 1 1 1
2 3
1 3
Output
464285719
450000005
882352949
Note

The answer to the first query of the first test case is $$$\frac{41}{28}$$$.

Problem Credits: Anonymous Red Panda