#include<stdio.h>
#define NR 666013
long long M[4][4],mm[4][4],m[4][4],nn;
void build(long x)
{ int i,j;
  long long 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=2;step<=x;step*=2)
  {
	 for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
		 mm[i][j]=((m[i][1]*m[1][j])%NR+(m[i][2]*m[2][j])%NR +(m[i][3]*m[3][j])%NR)%NR;
		 
	 for(i=1;i<=3;i++)
		for(j=1;j<=3;j++)
		  m[i][j]=mm[i][j];

	 if(x & step)
	 {	for(i=1;i<=3;i++)
		  for(j=1;j<=3;j++)
			  mm[i][j]=((M[i][1]*m[1][j])%NR+(M[i][2]*m[2][j])%NR+(M[i][3]*m[3][j])%NR)%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 %ld",&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;
}