#include<cstdio>

#include<cstdlib>

#include<iostream>

using namespace std;

#define ll long long

ll a[],ans2,ans5, x[],sum;

int qpow(int n,ll m,int Mod)

{

    int res=;n%=Mod;

    while(m){

        if(m&) res=n*res%Mod;

        n=n*n%Mod;

        m>>=;

    } return res;

}

void get(int opt,ll x,int sig)

{

    ll tmp=x;

    if(sig==||sig==-){

        if(tmp){

            a[opt]+=sig*(tmp/opt);

            tmp/=opt;

        }

        if(tmp){

            get(opt,tmp,*sig);    //5的倍数的系数不要搞忘

            get(opt,tmp,*sig);

        }

    }

    else{

        tmp=;

        for(int i=;i<opt;i++){

            tmp=tmp*i%opt;

        }

        tmp=qpow(tmp,x/opt,opt);

        for(ll i=(x/opt)*opt+;i<=x;i++)  tmp=tmp*(i%opt)%opt;

        if(opt==&&sig==)  a[]=a[]*tmp%opt;

        if(opt==&&sig==)  a[]=a[]*tmp%opt;

        if(opt==&&sig==-) a[]=a[]*tmp%opt;

        if(opt==&&sig==-) a[]=a[]*tmp%opt;

    }

}

int main()

{

    int T,n;

    scanf("%d",&T);

    while(T--){

        sum=; ans2=ans5=;

        a[]=a[]=; a[]=a[]=a[]=a[]=;

        scanf("%d",&n);

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

            scanf("%lld",&x[i]);

            sum+=x[i];

        }

        get(,sum,);    //正数表示在分子

        get(,sum,);

        get(,sum,);   //1表示2或5的幂，可以加。

        get(,sum,);   //1表示非2或5的幂。

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

            get(,x[i],-); //负数表示在分母

            get(,x[i],-);

            get(,x[i],-);

            get(,x[i],-);

        }

        if(a[]>&&a[]>){ //下面的可以不算，但是算也花不了多少时间。

            printf("0\n");

            continue;

        }

        ans2=qpow(,a[],);

        ans2=ans2*a[]%;

        ans2=ans2*qpow(a[],,)%;

        ans5=qpow(,a[],);

        ans5=ans5*a[]%;

        ans5=ans5*qpow(a[],,)%;

        printf("%lld\n",(*ans2+*ans5)%); //5和16都是逆元算的

    } return ;

}