哎这题有点意思。。

一开始肿么看都不理解题意，发现好多ACM题都这样，好多英文意思不能完全理解，只得照样例猜啦，猜不出来？？ 那就靠神队友解释了，囧。

就是排列，涂色使结果最大化。

反正别人的博客把这题的题意解释的很清楚了，我这只小牛就把自己的拙思路稍提一下。

也许做题多了马上就能感觉出这题当 a1,an,a2,an-1这样排列顺序效果会最大化，囧。

关键是代码实现的过程也很坎坷，自己一开始以为前面的减少的部分可能会与后面减少的部分有冲突，其实不然，还是自己没深入分析，，，

那这样就用总的情况减掉会有“冲突”的情况就行了。

除法取模，根本木有。。

要不就求逆元，可实际上不用，递推一下就OK了。

还有又顺便复习了一下取模过程中可能出现的溢出情况。。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

//除法取模显然有错误啊，都可能出来0了。。。

typedef __int64 LL;

LL a[1000005];

LL b[1000005];

LL sum1[1000005];

LL sum2[1000005];

LL min(LL a,LL b)

{

    if(a>b) return b;

    else return a;

}

const int maxn=1000000007;

int main()

{

    int case_num;

    scanf("%d",&case_num);

    while(case_num--)

    {

        int n;

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

            scanf("%I64d",&a[i]);

        sort(a+1,a+1+n);

        int temp1=1,temp2=n;

        for(int i=1;i<=n;i+=2)

            b[i]=a[temp1++];

        for(int i=2;i<=n;i+=2)

            b[i]=a[temp2--];

        sum1[0]=1;

        sum1[1]=b[1];

        sum2[n]=b[n];

        sum2[n+1]=1;

        for(int i=2;i<=n;i++)

        {

            sum1[i]=sum1[i-1]*b[i]%maxn;

        }

        for(int i=n-1;i>=1;i--)

        {

            sum2[i]=sum2[i+1]*b[i]%maxn;

        }

        long long ans=(sum1[n]%maxn)*(n%maxn)%maxn;

        long long temp=0;

        for(int i=2;i<=n;i++)

        {

            temp=(temp%maxn+(((min(b[i],b[i-1])*sum1[i-2])%maxn)*(sum2[i+1]%maxn))%maxn)%maxn;

        }

        ans=(ans-temp+maxn)%maxn;

        printf("%lld\n",ans);

    }

    return 0;

}