Background

Reimu is having a spell card duel with Marisa.

永夜の报い，Pixiv76062895，author: minusT. Please contact for removal.

Problem Description

Reimu has $n$ spell cards. Each card has a power value. For the $i$-th card, its power value is $a_i$. Now she wants to choose two spell cards and use them. Reimu finds that if she plays two spell cards $i, j$ at the same time, the damage dealt by these two spell cards will be $a_i\times a_j$.

There are power conflicts among these spell cards, and Reimu will tell you the compatibility of the spell cards. More specifically, there are $m$ relations among these spell cards, and each relation indicates that two spell cards are compatible. Note that if spell cards $i, j$ are compatible and spell cards $j, k$ are compatible, then spell cards $i, k$ are also compatible. If the two spell cards played are not compatible, then the damage they deal is $0$.

She is curious about what impact compatibility among spell cards will have, so she will ask you $q$ queries. Each time she gives you a pair of positive integers $l, r$, meaning that only the relations with indices in the interval $[l, r]$ will take effect.

Reimu does not want to bully Marisa too badly, so she will randomly pick two different spell cards from all spell cards to play. She wants to know, for each query, the expected damage modulo $10^9 + 7$.

Input Format

The first line contains three integers $n, m, q$, representing the total number of spell cards, the total number of relations among the spell cards, and the number of queries.

The next line contains $n$ positive integers, where the $i$-th integer is $a_i$.

The next $m$ lines each contain two positive integers $u_i, v_i$, indicating that spell card $u_i$ and spell card $v_i$ are compatible.

The next $q$ lines each contain two positive integers $l_i, r_i$, indicating the interval $[l_i, r_i]$ of relation indices in Reimu's query.

Output Format

Output $q$ lines in total. The $i$-th line contains one integer, representing, in the $i$-th query, the expected damage when randomly choosing two different spell cards, taken modulo $10^9 + 7$.

4 4 4
5 8 2 7 
3 1
1 4
3 2
1 4
2 4
1 2
2 3
3 3

500000012
833333349
500000012
666666674

14 16 15
1 2 7 3 2 4 6 2 5 7 2 4 3 3 
5 12
2 9
2 10
7 10
6 12
12 3
11 1
4 8
1 13
6 8
6 10
4 1
1 10
12 11
3 5
9 7
14 14
2 16
5 6
2 3
5 10
1 6
5 16
13 15
1 2
3 7
3 4
14 14
3 7
6 7
11 14

318681321
263736277
868131875
725274731
32967035
384615390
637362648
780219786
967032974
406593411
208791211
318681321
406593411
945054952
681318687

Hint

Sample 1 Explanation

For the third query, only the two pairs $(1, 4)$ and $(2, 3)$ of spell cards are compatible.

If the chosen spell cards are $(1, 2)$, then they are not compatible and the damage is $0$. The probability of this case is $\dfrac16$.

If the chosen spell cards are $(1, 3)$, then they are not compatible and the damage is $0$. The probability of this case is $\dfrac16$.

If the chosen spell cards are $(1, 4)$, they are compatible, and the damage is $a_1\times a_4 = 35$. The probability of this case is $\dfrac16$.

If the chosen spell cards are $(2, 3)$, they are compatible, and the damage is $a_2\times a_3 = 16$. The probability of this case is $\dfrac16$.

If the chosen spell cards are $(2, 4)$, then they are not compatible and the damage is $0$. The probability of this case is $\dfrac16$.

And so on. In the end, the expected value is $\dfrac{17}{2}$, which equals $500000012$ modulo $10^9 + 7$.

Constraints

This problem uses bundled testdata.

For all testdata, $1\le n, q\le 10^5, 1\le m\le 2n, 1\le a_i\le 10^9, 1\le l_i\le r_i\le m, 1\le u_i, v_i\le n$.

For different subtasks, we use the following settings:

• Special Property A: It is guaranteed that $u_i = 1, v_i = i + 1, m = n - 1$.
• Special Property B: It is guaranteed that $l_i = 1$.

Translated by ChatGPT 5