#include<stdio.h>
#define NR 666013
long long M[4][4],mm[4][4],m[4][4],nn;
void build(long long x)
{ int i,j,k,step;

  if(x%2==1)
	 for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
		  M[i][j]=m[i][j];
		  
  else { M[1][2]=M[1][3]=M[2][1]=M[2][3]=M[3][1]=M[3][2]=0;
         M[1][1]=M[2][2]=M[3][3]=1;
       }  
  for(step=1;(1<<step) <=x;step++)
  {
	 for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
		{ mm[i][j]=0;
		  for(k=1;k<=3;k++)
			 mm[i][j]=(mm[i][j]+m[i][k]*m[k][j])%NR;
		}
	 for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
		  m[i][j]=mm[i][j];

	 if(x & (1<<step))
	 {	for(i=1;i<=3;i++)
		  for(j=1;j<=3;j++)
			{ mm[i][j]=0;
			  for(k=1;k<=3;k++)
			  mm[i][j]=(mm[i][j]+M[i][k]*m[k][j])%NR;
			}
	  for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
		  M[i][j]=mm[i][j];
	 }
  }

}


void READ()
{  int i,t,x,y,z,a,b,c;
	long n;
	FILE *f,*g;
	f=fopen("iepuri.in","r");
	g=fopen("iepuri.out","w");
	fscanf(f,"%d",&t);
	for(i=1;i<=t;i++)
	{
	  fscanf(f,"%d %d %d %d %d %d %lld",&x,&y,&z,&a,&b,&c,&n);
	  m[1][1]=0; m[1][2]=1; m[1][3]=0;
	  m[2][1]=0; m[2][2]=0; m[2][3]=1;
	  m[3][1]=c; m[3][2]=b; m[3][3]=a;
	  build(n);
	  nn=(M[1][1]*x+M[1][2]*y+M[1][3]*z)%NR;
      fprintf(g,"%lld\n",nn);
	}
	fclose(f);
	fclose(g);
}
int main()
{
READ();
return 0;
}