P10268 Spell Card Duel.

Reimu is having a spell card duel with Marisa.  > 永夜の报い，Pixiv76062895，author: minusT. Please contact for removal.

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$.

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 $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$.

#### 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: | Subtask ID | $n$ | $q$ | Special Property | Score | | ---------- | ----------- | ----------- | ---------------- | ----- | | $0$ | $\le300$ | $\le300$ | None | $5$ | | $1$ | $\le 2000$ | $\le 2000$ | A | $10$ | | $2$ | $\le 2000$ | $\le 2000$ | B | $5$ | | $3$ | $\le 2000$ | $\le 2000$ | None | $10$ | | $4$ | $\le 30000$ | $\le 30000$ | None | $10$ | | $5$ | $\le 50000$ | $\le 50000$ | A | $10$ | | $6$ | $\le 50000$ | $\le 50000$ | B | $10$ | | $7$ | $\le 50000$ | $\le 50000$ | None | $15$ | | $8$ | $\le 10^5$ | $\le 10^5$ | None | $25$ | - **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