问题 H: 天使

残酷な天使のように 少年よ神話になれ

题目描述

Umiri 正在驾驶八号机歼灭使徒，现在有 $n$ 个使徒，第 $i$ 个使徒的能量为 pipi 。

任意两个使徒之间都可能互相接触并产生爆炸，若一次接触中两个使徒的能量分别为 $a,b$ ，那么爆炸将会产生 $a\times b$ 的破坏值，并且两个使徒将会融合成一个能量为 $a+b$ 的使徒。在若干次接触之后（使徒是否是为融合得到不影响使徒之间互相接触），会剩余最后一个使徒，记最后产生的总破坏值为 $S$ 。

Umiri 想知道在所有不同的使徒接触方式中， $S$ 的最大值是多少，并且她还想知道有多少种接触方式可以得到 $S$ 。

由于这两个数可能很大，因此你需要求出这两个数字对 109+7109+7 取模后的结果。

第一行输入一个正整数 $T（1\le T\le 10）$ ，表示数据组数。

对于每一组数据：

第一行输入一个正整数 n（2≤n≤2×105）n（2≤n≤2×105） ，表示使徒数量。

第二行输入 $n$ 个正整数 ai（1≤ai≤109）ai（1≤ai≤109） ，表示每个使徒的能量。

数据保证 ∑n≤2×106∑n≤2×106 。

第1种接触方式：第1个使徒和第2个使徒接触，产生1*1的破坏值，然后这个使徒与第3个使徒接触，产生1*2的破坏值，共产生1+2=3的破坏值。

第2种接触方式：第1个使徒和第3个使徒接触，产生1*1的破坏值，然后这个使徒与第2个使徒接触，产生1*2的破坏值，共产生1+2=3的破坏值。

第3种接触方式：第2个使徒和第3个使徒接触，产生1*1的破坏值，然后这个使徒与第1个使徒接触，产生1*2的破坏值，共产生1+2=3的破坏值。

最大的破坏值之和为3，共有3种方法可以产生这个最大值。