#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];

ofstream fout("iepuri.out");
void 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;(1<<i)<=N-2;i++)
    {
        if(((1<<i)&(N-2))>0)
        {for(ii=1;ii<=3;ii++)
          for(jj=1;jj<=3;jj++)
           {aux[ii][jj]=0;
           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];


        }

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