Compatible Spell Cards

You are given n spell cards, where the i-th card has an ability value \(a_i\). When two cards \(i\) and \(j\) are played together, they deal damage equal to \(a_i \times a_j\>, provided that the two cards are compatible. Otherwise, they deal 0 damage.

The compatibility between cards is defined by m relationships. Each relationship connects two cards. Importantly, if card \(i\) is compatible with card \(j\) and card \(j\) is compatible with card \(k\), then card \(i\) is also compatible with card \(k\) (i.e. the relation is transitive and thus forms an equivalence relation among cards).

You will be given q queries. Each query consists of two integers \(l\) and \(r\). For a query, only the relationships whose indices are in the range \([l, r]\) (inclusive) are activated. With the active relationships, the cards form several connected components (via DSU) and only pairs from the same component are considered compatible.

After the active relationships have been set, a pair of two different cards is chosen uniformly at random from all \(n\) cards. The expected damage is computed as the sum of \(a_i \times a_j\) over all compatible pairs divided by \(\binom{n}{2}\). You are to compute the expected damage modulo \(10^9+7\>.

More formally, for each query, let the activated graph partition the cards into components. For a component with a total ability sum \(S\) and individual abilities \(a_i\) in it, the total damage contributed by that component is \(\frac{S^2 - \sum a_i^2}{2}\). Let \(T\) be the sum of damages over all components. The answer for the query is \(T \times \text{inv}\left(\binom{n}{2}\right) \bmod (10^9+7)\), where \(\text{inv}(x)\) denotes the modular inverse of \(x\) modulo \(10^9+7\>.

inputFormat

The input begins with two integers n and m (n \ge 2).

The second line contains n integers \(a_1, a_2, \ldots, a_n\) representing the ability values of the cards.

Each of the next m lines contains two integers \(u\) and \(v\) (1-indexed) representing a compatibility relationship between card \(u\) and card \(v\). The relationships are numbered from 1 to m in the order they are given.

The next line contains a single integer q indicating the number of queries.

Each of the next q lines contains two integers \(l\) and \(r\) (1-indexed) indicating that only the relationships with indices in the range \([l, r]\) are active for that query.

outputFormat

For each query, output a single integer denoting the expected damage modulo \(10^9+7\>.

sample

3 2
1 2 3
1 2
2 3
1
1 2

666666675