#include<stdio.h>
long long int n,x,y,z,i,j,aux,a,b,c,T,xx[6],A,B,C;
int main()
{	FILE *f=fopen("iepuri.in","r");
	FILE *g=fopen("iepuri.out","w");
	fscanf(f,"%lld",&T);
	for(i=1;i<=T;i++)
	{	fscanf(f,"%lld%lld%lld%lld%lld%lld%lld",&xx[0],&xx[1],&xx[2],&A,&B,&C,&n);
		xx[3]=(A*xx[2]+B*xx[1]+C*xx[0])%666013;
		xx[4]=(A*xx[3]+B*xx[2]+C*xx[1])%666013;
		xx[5]=(A*xx[4]+B*xx[3]+C*xx[2])%666013;
		if(n>5)
		{ a=(A*A+2*B)%666013;
		  b=(2*A*C-B*B+2*666013)%666013;
		  c=(C*C)%666013;
		  if(n%2)
		   { x=xx[1];y=xx[3];z=xx[5];
		     for(j=7;j<=n;j=j+2)
		     { aux=(a*z+b*y+c*x)%666013; x=y; y=z; z=aux;}
		   }
		  else
		   { x=xx[0];y=xx[2];z=xx[4];
		     for(j=6;j<=n;j=j+2)
		     { aux=(a*z+b*y+c*x)%666013; x=y; y=z; z=aux;}
		   }
		fprintf(g,"%lld\n",z%666013);
		}
		else fprintf(g,"%lld\n",xx[n]);
	}
	fcloseall();
	return 0;
}