Problem Background

Reimu is having a spell card duel with Marisa.

"The Reward of the Eternal Night," Pixiv76062895, author is minusT, apologies for any infringement.

Problem Description

Reimu has a total of $n$ spell cards, each with a power value. For the $i$-th card, its power value is $a_i$. She wants to select two spell cards from them to use. Reimu has found that if she simultaneously uses two spell cards $i$ and $j$, the damage caused by these two cards will be $a_i \times a_j$.

There are conflicts between these spell cards. Reimu will inform you about the compatibility of these cards. Specifically, there are $m$ relationships between these cards, indicating that certain pairs of cards are compatible. Note that if cards $i$ and $j$ are compatible and cards $j$ and $k$ are compatible, then cards $i$ and $k$ are also compatible. If the two cards used are not compatible, the damage they cause is $0$.

She is curious about the impact of the compatibility between the spell cards, so she will ask you $q$ times. Each time, she will tell you a pair of positive integers $l$ and $r$, meaning that only the relationships within the interval $[l, r]$ are effective.

Reimu doesn't want to overwhelm Marisa too much, so she will randomly select two different spell cards from all the cards to use. She wants to know the expected value of the damage caused by each query, modulo $10^9 + 7$.

Input Format

The first line contains three integers $n$, $m$, and $q$, representing the total number of spell cards, the total number of relationships between the cards, and the number of queries from Reimu, respectively.

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

The following $m$ lines each contain two positive integers $u_i$ and $v_i$, indicating that the $u_i$-th card and the $v_i$-th card are compatible.

The next $q$ lines each contain two positive integers $l_i$ and $r_i$, representing the interval $[l_i, r_i]$ of the query from Reimu.

Output Format

A total of $q$ lines, with the $i$-th line containing an integer representing the expected value of the damage caused by the $i$-th query, modulo $10^9 + 7$, when two different spell cards are randomly selected.

Sample Input and Output

Input Sample #1

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

Output Sample #1

500000012
833333349
500000012
666666674

Input Sample #2

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

Output Sample #2

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

Notes

Sample 1 Explanation

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

If the selected cards are $(1, 2)$, they are not compatible, and the damage value is $0$, with a probability of $\dfrac{1}{6}$.

If the selected cards are $(1, 3)$, they are not compatible, and the damage value is $0$, with a probability of $\dfrac{1}{6}$.

If the selected cards are $(1, 4)$, they are compatible, and the damage value is $a_1 \times a_4 = 35$, with a probability of $\dfrac{1}{6}$.

If the selected cards are $(2, 3)$, they are compatible, and the damage value is $a_2 \times a_3 = 16$, with a probability of $\dfrac{1}{6}$.

If the selected cards are $(2, 4)$, they are not compatible, and the damage value is $0$, with a probability of $\dfrac{1}{6}$.

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

Data Range

This problem uses batched testing.

For all data, $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 have the following agreements:

• Special Property A: Guarantees $u_i = 1, v_i = i + 1, m = n - 1$.
• Special Property B: Guarantees $l_i = 1$.

见题面 Input 部分

见题面 Output 部分