#include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 const ll MOD=1e9+;

 const int N=;

 int f[N][],a[N],lg[N],cas,n;

 ll ans;

 ll inv[N];

 int query(int l,int r)

 {

     int len=r-l+;

     int q=lg[len];

     if (a[f[l][q]]>=a[f[r-(<<q)+][q]]) return f[l][q];

      else return f[r-(<<q)+][q];

 }

 void solve(int l,int r)

 {

     ans=ans*inv[r-l+]%MOD;

     int mid=query(l,r);

     if(l<mid) solve(l,mid-);

     if(mid<r) solve(mid+,r);

 }

 int main()

 {

     freopen("1008.in","r",stdin);

     freopen("1008.out","w",stdout);

     cas=read();

     for(int i=;i<=;i++) lg[i]=lg[i>>]+;

     inv[]=inv[]=;

     for(int i=;i<=;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;

     while(cas--)

     {

       n=read();

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

       {

         a[i]=read();

         f[i][]=i;

       }

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

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

         if(a[f[j][i-]]>=a[f[j+(<<(i-))][i-]]) f[j][i]=f[j][i-];

          else f[j][i]=f[j+(<<(i-))][i-];

       ans=;

       solve(,n);

       ans=ans*inv[]%MOD*n%MOD;

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

     }

     return ;

 }