题目背景

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

永夜の报い，Pixiv76062895，作者是 minusT，侵删。

题目描述

灵梦一共有 $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$ 取模后是多少。

输入格式

第一行三个整数 $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]$。

输出格式

一共 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问中，随机选择两张不同的符卡，造成伤害的期望值对 $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

提示

样例 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$。

对于不同的子任务，我们如下约定：

• 特殊性质 A：保证 $u_i = 1, v_i = i + 1, m = n - 1$。
• 特殊性质 B：保证 $l_i = 1$。