#include<stdio.h>
long long int n,x,y,z,i,j,aux,a,b,c,T,x0,x1,x2,x3,x4,x5,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",&x0,&x1,&x2,&A,&B,&C,&n);
		x3=(A*x2+B*x1+C*x0)%666013;
		x4=(A*x3+B*x2+C*x1)%666013;
		x5=(A*x4+B*x3+C*x2)%666013;
		if(n>5){ a=A*A+B;b=2*A*C-B*B;c=C*C;
			 if(n){x=x1;y=x3;z=x5;n++;n/=2;}
			} else {x=x0;y=x2;z=x4;n/=2;}
		for(j=3;j<=n;j++){ aux=(a*z+b*y+c*x)%666013; x=y; y=z; z=aux;}
		fprintf(g,"%lld\n",z%666013);
	}
	fcloseall();
	return 0;
}