← 返回题目列表

Codeforces · 2008/F

F. 樱子的盒子

中文机器翻译题面 查看原题

Sakurako 有一个盒子,里面有 $$$n$$$ 球。每个球都有它的价值。她想和朋友打赌,如果朋友从盒子里随机取出两个球(可能是两个不同的球,但它们的值可能相同),它们的值的乘积将与樱子猜中的数字相同。

由于樱子拥有概率博士学位,她知道最好选择的数字就是期望值,但她忘记了如何计算它。帮助樱子找出数组中两个元素的乘积的期望值。

可以看出,期望值的形式为 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 是非负整数,$$$Q \ne 0$$$。报告 $$$P \cdot Q^{-1}(\bmod 10^9+7)$$$ 的值。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 数组中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i\le 10^9$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$P \cdot Q^{-1}(\bmod 10^9+7)$$$ 的值。

示例

输入 #1

3
3
3 2 3
4
2 2 2 4
5
1 2 3 4 5

输出 #1

7
6
500000012

注意

对于第一个测试,樱子的朋友可以选择以下几对球:$$$(a_1,a_2)$$$、$$$(a_1,a_3)$$$、$$$(a_2,a_3)$$$。它们的乘积分别等于 $$$3\cdot 2=6$$$ 、 $$$3\cdot 3=9$$$ 、 $$$3\cdot 2=6$$$ ,因此期望值为 $$$\frac{6+9+6}{3}=7$$$ 。

对于第二次测试,樱子的朋友可以选择以下这对球:$$$(a_1,a_2)$$$、$$$(a_1,a_3)$$$、$$$(a_1,a_4)$$$、$$$(a_2,a_3)$$$、$$$(a_2,a_4)$$$、 $$$(a_3,a_4)$$$。它们的乘积分别等于 $$$2\cdot 2=4$$$ 、 $$$2\cdot 2=4$$$ 、 $$$2\cdot 4=8$$$ 、 $$$2\cdot 2=4$$$ 、 $$$2\cdot 4=8$$$ 、 $$$2\cdot 4=8$$$ ,因此期望值为$$$\frac{4+4+8+4+8+8}{6}=\frac{36}{6}=6$$$。