#include<stdio.h>
#define fin  "iepuri.in"
#define fout "iepuri.out"
#define Mod 666013
int n,t,m[4][4];
int templ[4][4]={ 0 , 0 , 0 , 0 ,
		  0 , 0 , 1 , 0 ,
		  0 , 0 , 0 , 1 ,
		  0 , 0 , 0 , 0 };
FILE *in,*out;

void init(int mat[][4],int a,int b,int c) {
int i,j;
	for (i=1;i<4;++i)
	for (j=1;j<4;++j) mat[i][j]=templ[i][j];

	m[3][1]=c; m[3][2]=b; m[3][3]=a;
}

void unit(int mat[][4]) {
int i,j;
	for (i=1;i<4;++i)
	for (j=1;j<4;++j) 
		if (i==j) 
			mat[i][j]=1;
		else 
			mat[i][j]=0;
}

void mult(int a[][4],int b[][4]) {
int i,j,c[4][4];
	for (i=1;i<4;++i)
	for (j=1;j<4;++j) {
		c[i][j]=(a[i][1]*b[1][j])%Mod;
		c[i][j]=(c[i][j] + a[i][2]*b[2][j]%Mod)%Mod;
	        c[i][j]=(c[i][j] + a[i][3]*b[3][j]%Mod)%Mod; 
	}
	for (i=1;i<4;++i)
	for (j=1;j<4;++j) 
		a[i][j]=c[i][j]; 

}

int main() {
int i,j,x,y,z,a,b,c;
int sol,ans[4][4];
	
	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%i",&t);

	for (i=1;i<=t;++i) {

		fscanf(in,"%i%i%i",&x,&y,&z);
		fscanf(in,"%i%i%i%i",&a,&b,&c,&n);
		
		init(m,a,b,c);

		if (n&1) 
			init(ans,a,b,c);
		else
		       	unit(ans);

		for (j=2;j<=n;j=j<<1) {
			mult(m,m);

			if (n&j) 
				mult(ans,m);
		}

		//for (int ii=1;ii<4;++ii) {
	//		for (j=1;j<4;++j) printf("%i ",ans[ii][j]);
	//		printf("\n");
	//	}

		sol=ans[1][1]*x%Mod;
		sol=(sol+ans[1][2]*y%Mod)%Mod;
		sol=(sol+ans[1][3]*z%Mod)%Mod;

		fprintf(out,"%i\n",sol);
	}

	fclose(in); fclose(out);

	return 0;
}