#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

#define mod 666013;
long long T,X,Y,Z,A,B,C,N,a[50][50],sol[50][50],aux[50][50];

ofstream fout("iepuri.out");
void solve()
{
long long i,j,k,ii,jj,kk;
    memset(a,0,sizeof(a));
    memset(sol,0,sizeof(sol));
    memset(aux,0,sizeof(aux));
    a[2][1]=a[3][2]=1;
    a[1][1]=A;
    a[1][2]=B;
    a[1][3]=C;
    sol[1][1]=1;
    sol[2][2]=1;
    sol[3][3]=1;

    for(i=0;(1<<i)<=N-2;i++)
    {memset(aux,0,sizeof(aux));
        if(((1<<i)&(N-2))>0)
        {for(ii=1;ii<=3;ii++)
          for(jj=1;jj<=3;jj++)
           {
           for(kk=1;kk<=3;kk++)
               aux[ii][jj]=(aux[ii][jj]+sol[ii][kk]*a[kk][jj])%mod;

           }
          for(ii=1;ii<=3;ii++)
          for(jj=1;jj<=3;jj++)
          sol[ii][jj]=aux[ii][jj];
          memset(aux,0,sizeof(aux));

        }

     for(ii=1;ii<=3;ii++)
      for(jj=1;jj<=3;jj++)
      {
      for(kk=1;kk<=3;kk++)
       aux[ii][jj]=(aux[ii][jj]+a[ii][kk]*a[kk][jj])%mod;
      }
      for(ii=1;ii<=3;ii++)
        for(jj=1;jj<=3;jj++)
          a[ii][jj]=aux[ii][jj]%mod;
     }

     fout<<(sol[1][1]*Z+sol[1][2]*Y+sol[1][3]*X)%mod;
     fout<<"\n";

}

void cit()
{long long i;
ifstream fin("iepuri.in");
fin>>T;
for(i=1;i<=T;i++)
 {fin>>X>>Y>>Z>>A>>B>>C>>N;

 solve();
 }
 fin.close();

}

int main()
{
    cit();
    fout.close();
    return 0;
}