灵梦一共有 $n$ 张符卡，每张卡都有一个能力值，对于第 $i$ 张卡，它的能力值为 $a_i$，现在她想从中选出两张符卡并使用它们，灵梦发现，如果她同时打出了两张符卡 $i, j$，这两张符卡造成的伤害将会是 $a_i\times a_j$。
这些符卡之间有能力的冲突，灵梦会告诉你这些符卡的兼容性，具体而言这些符卡之间有 $m$ 条关系，这些关系表明某两张符卡之间是兼容的，**注意**，如果符卡 $i, j$ 兼容且符卡 $j, k$ 兼容，那么符卡 $i, k$ 也是兼容的，如果打出的两张符卡之间不是兼容的，那么它们造成的伤害为 $0$。
她很好奇符卡之间的兼容性会造成什么样的影响，所以她会询问你 $q$ 次，每次告诉你一对正整数 $l, r$，意味着只有编号在区间 $[l, r]$ 内的关系才会生效。
灵梦不想把魔理沙虐得太惨，所以她会随机从所有符卡中选出两张**不同**的符卡来打出，她想知道每次询问造成的伤害的期望值对 $10^9 + 7$ 取模后是多少。
## Input
第一行三个整数 $n, m, q$ 分别表示符卡总数，符卡间的关系总数，灵梦的询问次数。
接下来一行 $n$ 个正整数，第 $i$ 个表示 $a_i$。
接下来 $m$ 行，每行两个正整数 $u_i, v_i$，表示第 $u_i$ 张符卡与第 $v_i$ 张符卡是兼容的。
接下来 $q$ 行，每行两个正整数 $l_i, r_i$，表示灵梦询问的编号区间 $[l_i, r_i]$。
## Output
一共 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问中，随机选择两张**不同**的符卡，造成伤害的期望值对 $10^9 + 7$ 取模后的结果。
[samples]
## Background
灵梦正在和魔理沙进行符卡对决。
> 永夜の报い，Pixiv76062895，作者是 minusT，侵删。
## Note
#### 样例 1 解释
对于第三组询问，只有 $(1, 4), (2, 3)$ 两对符卡之间是兼容的。
如果选择的符卡是 $(1, 2)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\dfrac16$。
如果选择的符卡是 $(1, 3)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\dfrac16$。
如果选择的符卡是 $(1, 4)$，它们兼容，伤害值为 $a_1\times a_4 = 35$，这种情况的概率是 $\dfrac16$。
如果选择的符卡是 $(2, 3)$，它们兼容，伤害值为 $a_2\times a_3 = 16$，这种情况的概率是 $\dfrac16$。
如果选择的符卡是 $(2, 4)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\dfrac16$。
以此类推，最终的期望值是 $\dfrac{17}{2}$，其在模 $10^9 + 7$ 意义下等于 $500000012$。
#### 数据范围
**本题采用捆绑测试。**
对于所有数据，$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$。
对于不同的子任务，我们如下约定：
| 子任务编号 | $n$ | $q$ | 特殊性质 | 子任务分值 |
| ---------- | ----------- | ----------- | -------- | ---------- |
| $0$ | $\le300$ | $\le300$ | 无 | $5$ |
| $1$ | $\le 2000$ | $\le 2000$ | A | $10$ |
| $2$ | $\le 2000$ | $\le 2000$ | B | $5$ |
| $3$ | $\le 2000$ | $\le 2000$ | 无 | $10$ |
| $4$ | $\le 30000$ | $\le 30000$ | 无 | $10$ |
| $5$ | $\le 50000$ | $\le 50000$ | A | $10$ |
| $6$ | $\le 50000$ | $\le 50000$ | B | $10$ |
| $7$ | $\le 50000$ | $\le 50000$ | 无 | $15$ |
| $8$ | $\le 10^5$ | $\le 10^5$ | 无 | $25$ |
- **特殊性质 A**：保证 $u_i = 1, v_i = i + 1, m = n - 1$。
- **特殊性质 B**：保证 $l_i = 1$。