#include <cstdio>
#define INF "iepuri.in"
#define OUF "iepuri.out"
#define MAX 4
#define LLI long long int
#define CLB 666013
void mcopy(LLI dest[][MAX],LLI src[][MAX])
{
   register int i,j;
   for(i=1;i<MAX;i++)
	   for(j=1;j<MAX;j++) dest[i][j]=src[i][j];
}
void boria(LLI b[][MAX],LLI a[][MAX],LLI rez[][MAX])
{
	register int i,j,k;
	for(i=1;i<MAX;i++)
		for(j=1;j<MAX;j++)
		{
			rez[i][j]=0;
			for(k=1;k<MAX;k++) rez[i][j]=(rez[i][j]+b[i][k]*a[k][j])%CLB;
		}
}
void mprint(LLI a[][MAX])
{
	register int i,j;
	for(i=1;i<MAX;i++)
	{
		for(j=1;j<MAX;j++) printf("%lld ",a[i][j]);
		printf("\n");
	}
	printf("\n");
}
int main()
{
   FILE *in,*out;
   in=fopen(INF,"r");
   out=fopen(OUF,"w");
   int i,t,j,k;
   LLI x,y,z,a,b,c,n,aux,m1[MAX][MAX]={0},m2[MAX][MAX],m3[MAX][MAX],sol[MAX]={0};
   m1[1][2]=1;m1[2][3]=1;
   LLI maux[MAX][MAX];

   fscanf(in,"%d",&t);
   for(i=1;i<=t;i++)
   {
	   fscanf(in,"%lld %lld %lld %lld %lld %lld %lld",&x,&y,&z,&a,&b,&c,&n);
	   m1[3][1]=c;m1[3][2]=b;m1[3][3]=a;
	   sol[1]=x;sol[2]=y;sol[3]=z;

	   aux=n+1;
	   if(aux<4) fprintf(out,"%lld\n",sol[aux]%CLB);
	   else
	   {
	//	   mprint(m1);
		   for(j=0;j<MAX;j++)
		      for(k=0;k<MAX;k++)
		              if(j==k) m3[j][k]=1;
		   		else m3[j][k]=0;		   
		   aux-=3;
//		   printf("AUX: %lld\n",aux);
		   mcopy(m2,m1);
		   while(aux)
		   {
			   if(aux%2)
			   {
				   boria(m3,m2,maux);
				   mcopy(m3,maux);
			   }
			   aux/=2;
			   boria(m2,m2,maux);
			   mcopy(m2,maux);

		   }
		   //mprint(m2);
	//	   mprint(m3);
                   maux[1][1]=maux[1][2]=maux[1][3]=0;
		   for(j=1;j<MAX;j++)
			   for(k=1;k<MAX;k++) maux[1][j]=(maux[1][j]+m3[j][k]*sol[k])%CLB;
		   fprintf(out,"%lld\n",maux[1][3]);
	   }
   }
   fclose(in);fclose(out);
   return 0;
}