题目背景
灵梦正在和魔理沙进行符卡对决。

永夜の报い,Pixiv76062895,作者是 minusT,侵删。
题目描述
灵梦一共有 n 张符卡,每张卡都有一个能力值,对于第 i 张卡,它的能力值为 ai,现在她想从中选出两张符卡并使用它们,灵梦发现,如果她同时打出了两张符卡 i,j,这两张符卡造成的伤害将会是 ai×aj。
这些符卡之间有能力的冲突,灵梦会告诉你这些符卡的兼容性,具体而言这些符卡之间有 m 条关系,这些关系表明某两张符卡之间是兼容的,注意,如果符卡 i,j 兼容且符卡 j,k 兼容,那么符卡 i,k 也是兼容的,如果打出的两张符卡之间不是兼容的,那么它们造成的伤害为 0。
她很好奇符卡之间的兼容性会造成什么样的影响,所以她会询问你 q 次,每次告诉你一对正整数 l,r,意味着只有编号在区间 [l,r] 内的关系才会生效。
灵梦不想把魔理沙虐得太惨,所以她会随机从所有符卡中选出两张不同的符卡来打出,她想知道每次询问造成的伤害的期望值对 109+7 取模后是多少。
输入格式
第一行三个整数 n,m,q 分别表示符卡总数,符卡间的关系总数,灵梦的询问次数。
接下来一行 n 个正整数,第 i 个表示 ai。
接下来 m 行,每行两个正整数 ui,vi,表示第 ui 张符卡与第 vi 张符卡是兼容的。
接下来 q 行,每行两个正整数 li,ri,表示灵梦询问的编号区间 [li,ri]。
输出格式
一共 q 行,第 i 行一个整数,表示第 i 次询问中,随机选择两张不同的符卡,造成伤害的期望值对 109+7 取模后的结果。
提示
样例 1 解释
对于第三组询问,只有 (1,4),(2,3) 两对符卡之间是兼容的。
如果选择的符卡是 (1,2),那么它们不兼容,伤害值为 0,这种情况的概率是 61。
如果选择的符卡是 (1,3),那么它们不兼容,伤害值为 0,这种情况的概率是 61。
如果选择的符卡是 (1,4),它们兼容,伤害值为 a1×a4=35,这种情况的概率是 61。
如果选择的符卡是 (2,3),它们兼容,伤害值为 a2×a3=16,这种情况的概率是 61。
如果选择的符卡是 (2,4),那么它们不兼容,伤害值为 0,这种情况的概率是 61。
以此类推,最终的期望值是 217,其在模 109+7 意义下等于 500000012。
数据范围
本题采用捆绑测试。
对于所有数据,1≤n,q≤105,1≤m≤2n,1≤ai≤109,1≤li≤ri≤m,1≤ui,vi≤n。
对于不同的子任务,我们如下约定:
子任务编号 |
n |
q |
特殊性质 |
子任务分值 |
0 |
≤300 |
无 |
5 |
1 |
≤2000 |
A |
10 |
2 |
B |
5 |
3 |
无 |
10 |
4 |
≤30000 |
5 |
≤50000 |
A |
6 |
B |
7 |
无 |
15 |
8 |
≤105 |
25 |
- 特殊性质 A:保证 ui=1,vi=i+1,m=n−1。
- 特殊性质 B:保证 li=1。