符卡对决

• 时间限制：3 秒
• 内存限制：512 MiB

题目背景

灵梦正在和魔理沙进行符卡对决。

题目描述

灵梦有 $n$ 张符卡，第 $i$ 张符卡的能力值为 $a_i$。如果同时打出两张不同的符卡 $i,j$，且它们兼容，那么造成的伤害为 $a_i\times a_j$；否则伤害为 $0$。

兼容关系具有传递性：若 $i,j$ 兼容且 $j,k$ 兼容，则 $i,k$ 也兼容。现有按输入顺序编号为 $1,2,\ldots,m$ 的 $m$ 条无向兼容关系。

共有 $q$ 次询问。一次询问给出 $l,r$，仅编号在 $[l,r]$ 内的关系生效。此时两张符卡兼容，当且仅当它们在这些关系构成的无向图中连通。

灵梦从全部 $\binom n2$ 对不同符卡中等概率选出一对。请对每次询问，求伤害期望在模 $10^9+7$ 意义下的值。

输入格式

第一行三个整数 $n,m,q$，分别表示符卡数、关系数和询问数。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，第 $i$ 行两个整数 $u_i,v_i$，表示第 $i$ 条无向兼容关系连接 $u_i,v_i$。

接下来 $q$ 行，每行两个整数 $l_i,r_i$，表示仅启用编号在 $[l_i,r_i]$ 内的关系。

输出格式

输出 $q$ 行。第 $i$ 行一个整数，表示第 $i$ 次询问的答案。

样例输入

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

样例说明

第三次询问仅启用第 $2,3$ 条关系，因此连通的不同符卡对为 $(1,4)$ 与 $(2,3)$。伤害总和为 $5\times7+8\times2=51$，除以 $\binom42=6$ 后得到 $17/2$，其模 $10^9+7$ 的值为 $500000012$。

数据范围

对于所有测试点：

• $2\le n\le10^5$；
• $1\le m\le2n$，$1\le q\le10^5$；
• $1\le a_i\le10^9$；
• $1\le u_i,v_i\le n$，关系中允许自环和重边；
• $1\le l_i\le r_i\le m$。

本题每个测试点独立计分，同一子任务内测试点等分。