解题思路

每次融合两团元魂，灵力值分别为 $x,y$，消耗为 $x \times y$，新灵力为 $x+y$。

关键结论：无论融合顺序如何，总消耗都相同。

原因如下：

假设最终所有元魂都会融合成一团。对于任意两个初始元魂 $a_i,a_j$，它们一开始分别在不同的元魂团中。随着融合过程进行，它们第一次被合并到同一个元魂团时，一定发生在某次融合两个大团的时候。

题目内容

在《忘川风华录》的喵居中，为了帮助名士猫完成进化，使君需要炼化出高阶的九世灵。

喵居的供台上目前散落着 $n$ 团微小的「猫灵元魂」，第 $i$ 团元魂的灵力值为 $a_i$。使君必须将所有元魂最终融合为 1 个完整的天品猫灵，每次融合操作，选择两团元魂（记灵力值分别为 $x,y$）进行汇聚：

• 消耗 $x \times y$，融合完成后生成一团新的元魂，其灵力值变为 $x + y$。

为了省下通宝去给陆游买更多的小鱼干，使君可以自由选择每一步融合的顺序。

请你求出将全部「猫灵元魂」融合成一个所需要的最小总消耗，并输出该最小总消耗对 $10^9 + 7$ 取模后的结果。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 2 \times 10^5$）代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$），代表供台上的猫灵元魂数量。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），代表每团元魂的初始灵力值。

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示炼化所需的最小总消耗对 $10^9 + 7$ 取模后的结果。

样例1

输入

2
3
1 2 3
4
2 2 2 2

输出

11
24

说明

对于第一组测试数据，陆游最满意的方案为：

• 融合灵力为 $1$ 和 $2$ 的元魂，消耗 $1 \times 2 = 2$，生成新元魂灵力为 $3$。
• 此时供台上剩下两个灵力为 $3$ 的元魂。再次融合它们，消耗 $3 \times 3 = 9$，生成最终灵力为 $6$ 的天品猫灵。

总消耗为 $2 + 9 = 11$。