#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;

#define LL long long int

const int MAXN = ;

const LL MOD = (1e9) + ;

int n;

LL a[MAXN];

LL b[MAXN];

void ExGcd( LL a, LL b, LL& d, LL& x, LL& y )

{

    if ( !b ) { d = a, x = , y = ; }

    else

    {

        ExGcd( b, a % b, d, y, x );

        y -= x * ( a / b );

    }

}

LL GetInverse( LL num )

{

    LL d, x, y;

    ExGcd( num, MOD, d, x, y );

    return ( x % MOD + MOD ) % MOD;

}

int main()

{

//    freopen( "1001.in", "r", stdin );

//    freopen( "s.out", "w", stdout );

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%d", &n );

        LL all = ;

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

        {

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

            b[i] = a[i];

            all *= a[i];

            all %= MOD;

        }

        //printf( "all = %I64d\n", all );

        sort( b, b + n );

        int i, j;

        for ( i = , j = ; i < n ; i += , ++j )

            a[i] = b[j];

        for ( i = , j = n - ; i < n; i += , --j )

            a[i] = b[j];

//        for ( int i = 0; i < n; ++i )

//            printf( "%I64d ", a[i] );

//        puts("");

        LL p = ;

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

        {

            LL tmp = ( all * GetInverse( ( a[i] * a[i - ] ) % MOD ) ) % MOD;

            p += ( min( a[i], a[i - ] ) * tmp ) % MOD ;

            p %= MOD;

        }

        all *= n;

        all %= MOD;

//        printf("p = %I64d\n", p );

        LL ans = ( all - p + MOD ) % MOD;

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

    }

    return ;

}