{"raw_statement":[{"iden":"background","content":"灵梦正在和魔理沙进行符卡对决。\n\n![Card](https://cdn.luogu.com.cn/upload/image_hosting/xu68nj8k.png)\n\n> 永夜の报い，Pixiv76062895，作者是 minusT，侵删。"},{"iden":"statement","content":"灵梦一共有 $n$ 张符卡，每张卡都有一个能力值，对于第 $i$ 张卡，它的能力值为 $a_i$，现在她想从中选出两张符卡并使用它们，灵梦发现，如果她同时打出了两张符卡 $i, j$，这两张符卡造成的伤害将会是 $a_i\\times a_j$。\n\n这些符卡之间有能力的冲突，灵梦会告诉你这些符卡的兼容性，具体而言这些符卡之间有 $m$ 条关系，这些关系表明某两张符卡之间是兼容的，**注意**，如果符卡 $i, j$ 兼容且符卡 $j, k$ 兼容，那么符卡 $i, k$ 也是兼容的，如果打出的两张符卡之间不是兼容的，那么它们造成的伤害为 $0$。\n\n她很好奇符卡之间的兼容性会造成什么样的影响，所以她会询问你 $q$ 次，每次告诉你一对正整数 $l, r$，意味着只有编号在区间 $[l, r]$ 内的关系才会生效。\n\n灵梦不想把魔理沙虐得太惨，所以她会随机从所有符卡中选出两张**不同**的符卡来打出，她想知道每次询问造成的伤害的期望值对 $10^9 + 7$ 取模后是多少。"},{"iden":"input","content":"第一行三个整数 $n, m, q$ 分别表示符卡总数，符卡间的关系总数，灵梦的询问次数。\n\n接下来一行 $n$ 个正整数，第 $i$ 个表示 $a_i$。\n\n接下来 $m$ 行，每行两个正整数 $u_i, v_i$，表示第 $u_i$ 张符卡与第 $v_i$ 张符卡是兼容的。\n\n接下来 $q$ 行，每行两个正整数 $l_i, r_i$，表示灵梦询问的编号区间 $[l_i, r_i]$。"},{"iden":"output","content":"一共 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问中，随机选择两张**不同**的符卡，造成伤害的期望值对 $10^9 + 7$ 取模后的结果。"},{"iden":"note","content":"#### 样例 1 解释\n\n对于第三组询问，只有 $(1, 4), (2, 3)$ 两对符卡之间是兼容的。\n\n如果选择的符卡是 $(1, 2)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\\dfrac16$。\n\n如果选择的符卡是 $(1, 3)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\\dfrac16$。\n\n如果选择的符卡是 $(1, 4)$，它们兼容，伤害值为 $a_1\\times a_4 = 35$，这种情况的概率是 $\\dfrac16$。\n\n如果选择的符卡是 $(2, 3)$，它们兼容，伤害值为 $a_2\\times a_3 = 16$，这种情况的概率是 $\\dfrac16$。\n\n如果选择的符卡是 $(2, 4)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\\dfrac16$。\n\n以此类推，最终的期望值是 $\\dfrac{17}{2}$，其在模 $10^9 + 7$ 意义下等于 $500000012$。\n\n#### 数据范围\n\n**本题采用捆绑测试。**\n\n对于所有数据，$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\n对于不同的子任务，我们如下约定：\n\n| 子任务编号 | $n$         | $q$         | 特殊性质 | 子任务分值 |\n| ---------- | ----------- | ----------- | -------- | ---------- |\n| $0$        | $\\le300$    | $\\le300$    | 无       | $5$        |\n| $1$        | $\\le 2000$  | $\\le 2000$  | A        | $10$       |\n| $2$        | $\\le 2000$  | $\\le 2000$  | B        | $5$       |\n| $3$        | $\\le 2000$  | $\\le 2000$  | 无       | $10$       |\n| $4$        | $\\le 30000$ | $\\le 30000$ | 无       | $10$       |\n| $5$        | $\\le 50000$ | $\\le 50000$ | A        | $10$       |\n| $6$        | $\\le 50000$ | $\\le 50000$ | B        | $10$       |\n| $7$        | $\\le 50000$ | $\\le 50000$ | 无       | $15$       |\n| $8$        | $\\le 10^5$  | $\\le 10^5$  | 无       | $25$       |\n\n- **特殊性质 A**：保证 $u_i = 1, v_i = i + 1, m = n - 1$。\n- **特殊性质 B**：保证 $l_i = 1$。\n"}],"translated_statement":null,"sample_group":[["4 4 4\n5 8 2 7 \n3 1\n1 4\n3 2\n1 4\n2 4\n1 2\n2 3\n3 3","500000012\n833333349\n500000012\n666666674"],["14 16 15\n1 2 7 3 2 4 6 2 5 7 2 4 3 3 \n5 12\n2 9\n2 10\n7 10\n6 12\n12 3\n11 1\n4 8\n1 13\n6 8\n6 10\n4 1\n1 10\n12 11\n3 5\n9 7\n14 14\n2 16\n5 6\n2 3\n5 10\n1 6\n5 16\n13 15\n1 2\n3 7\n3 4\n14 14\n3 7\n6 7\n11 14","318681321\n263736277\n868131875\n725274731\n32967035\n384615390\n637362648\n780219786\n967032974\n406593411\n208791211\n318681321\n406593411\n945054952\n681318687"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}