题目描述
有一个数列 {an}。
你每次可以选择任意 k(k≥2)个数，这 k 个数的和 S 会成为你这次操作的得分。操作结束后，你要把这 k 个数在数组中删除，然后在数组中加入 S。操作数可以为 0 (如{-1,-2,-2022}时可以选择不操作直接输出0)，求最大总得分。
输入
第一行一个整数 T (1<=T<=20) ，表示数据组数。
对于每组数据：
- 第一行一个数 n (2<=n<=2×103) ，表示数列长度。
- 接下来一行 n 个数 ai (-103<=ai<=103) ，表示这个数列 {an}。
对于每组数据：
- 第一行一个数 n (2<=n<=2×103) ，表示数列长度。
- 接下来一行 n 个数 ai (-103<=ai<=103) ，表示这个数列 {an}。
输出
对于每组数据，仅一行一个数，即最大总得分。
由于结果可能较大，你只需要输出答案对 107+7 取模的值。
由于结果可能较大，你只需要输出答案对 107+7 取模的值。
样例输入 Copy
3
4
2 -1 1 3
3
-1 -1 3
3
-1 -2 -2022
样例输出 Copy
16
3
0
提示
样例 1 说明
- 第三次，选择 [ -1, 6]，S=5。
- 结束游戏。
总得分 5+6+5=16。
样例2说明
- 第一次，选择 [ −1, -1, 3]，S=2，数列变为 [−1,1,5]。
- 第二次，选择 [ -1, 2]，S=1。
- 结束游戏。
总得分 2+1=3。
- 第一次，选择 [ 2, −1, 1, 3]，S=5，数列变为 [−1,1,5]。
- 第二次，选择 [ −1, 1, 5]，S=6，数列变为 [−1,6]。- 第三次，选择 [ -1, 6]，S=5。
- 结束游戏。
总得分 5+6+5=16。
样例2说明
- 第一次，选择 [ −1, -1, 3]，S=2，数列变为 [−1,1,5]。
- 第二次，选择 [ -1, 2]，S=1。
- 结束游戏。
总得分 2+1=3。
样例 3 说明
不作操作，得分 0。