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

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


long long solve()
{
long long i,j,k,ii,jj,kk;
    for(i=1;i<=3;i++)
    for(j=1;j<=3;j++)
    a[i][j]=sol[i][j]=aux[i][j]=0;
    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;(1LL<<i)<=N-2;i++)
    {
        if(((1LL<<i)&(N-2))>0)
        { memset(aux,0,sizeof(aux));
        for(kk=1;kk<=3;kk++)
        for(ii=1;ii<=3;ii++)
          for(jj=1;jj<=3;jj++)
           {

               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(kk=1;kk<=3;kk++)
     for(ii=1;ii<=3;ii++)
      for(jj=1;jj<=3;jj++)
      {
       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;
     }

     return (sol[1][1]*Z+sol[1][2]*Y+sol[1][3]*X)%mod;


}



int main()
{
    long long i,ret;
 ofstream fout("iepuri.out");
ifstream fin("iepuri.in");
fin>>T;
for(i=1;i<=T;i++)
 {fin>>X>>Y>>Z>>A>>B>>C>>N;

 ret=solve();
 fout<<ret<<'\n';
 }
 fin.close();
    fout.close();
    return 0;
}