#include<cstdio>
#include<cstring>

const int MOD=666013;

void inmultire(int rasp[3][3],int a[3][3],int b[3][3])
{
 for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
         for(int k=0;k<3;k++)
             rasp[i][j]=(rasp[i][j]+(1LL*a[i][k]*b[k][j])%MOD)%MOD;
}

void copiere(int source[3][3],int destination[3][3])
{
 memcpy(destination,source,3*3*(sizeof(int)));
}

void put(int a[3][3],int rasp[3][3],int k)
{
 if(k==0)
    {
     rasp[0][0]=rasp[1][1]=rasp[2][2]=1;
     return;
    }
 if(k==1)
    {
     copiere(a,rasp);
     return;
    }
 int b[3][3],c[3][3];
 memset(c,0,sizeof c);
 memset(b,0,sizeof b);
 put(a,b,k/2);
 inmultire(c,b,b);
 if(k%2==1)
    inmultire(rasp,a,c);
 else
    copiere(c,rasp);
}

int Rezolva(int x,int y,int z,int a,int b,int c,int k)
{
 int M0[3][3]={{x,y,z},{0,0,0},{0,0,0}},Z[3][3]={{0,0,c},{1,0,b},{0,1,a}};
 int rasp[3][3];
 if(k<3)
    return M0[0][k];
 memset(rasp,0,sizeof rasp);
 put(Z,rasp,k-2);
 copiere(rasp,Z);
 memset(rasp,0,sizeof rasp);
 inmultire(rasp,M0,Z);
 return rasp[0][2];
}

int main()
{
 FILE *in=fopen("iepuri.in","r");
 int nr_teste;
 fscanf(in,"%d ",&nr_teste);
 FILE *out=fopen("iepuri.out","w");
 for(int test=1;test<=nr_teste;test++)
     {
      int x,y,z,a,b,c,k;
      fscanf(in,"%d %d %d %d %d %d %d ",&x,&y,&z,&a,&b,&c,&k);
      int rasp=Rezolva(x,y,z,a,b,c,k);
      fprintf(out,"%d\n",rasp);
     }
 fclose(in);
 fclose(out);
 return 0;
}