//explicatie prezentata aici: http://infoarena.ro/preoni-2005/runda-1/solutii
#include<cstdlib>
#include<cstdio>
#define nr 666013
int x,y,z,a,b,c;
long long m[4][4],rez[4][4];

void initm(){
	m[0][0]=0;
	m[0][1]=1;
	m[0][2]=0;
	m[1][0]=0;
	m[1][1]=0;
	m[1][2]=1;
}
	
void initrez(){
	rez[0][0]=rez[1][1]=rez[2][2]=1;
	rez[0][1]=rez[0][2]=rez[1][0]=rez[1][2]=rez[2][0]=rez[2][1]=0;
}
void inmrez(){
	int i,j,c[3][3],k;
	for(i=0;i<=2;i++)
		 for(j=0;j<=2;j++)
			 {
			  c[i][j]=0;
			  for(k=0;k<=2;k++)
			  {c[i][j]=(c[i][j]+m[i][k]*rez[k][j]%nr)%nr;
				}
     }
for(i=0;i<=2;i++)
		 for(j=0;j<=2;j++)
			 rez[i][j]=c[i][j];
}
void inmm(){
	int i,j,k;
	long long c[3][3];
	for(i=0;i<=2;i++)
		 for(j=0;j<=2;j++)
			 {
			  c[i][j]=0;
			  for(k=0;k<=2;k++)
			  {c[i][j]=(c[i][j]+m[i][k]*m[k][j]%nr)%nr;
				}
     }
for(i=0;i<=2;i++)
		 for(j=0;j<=2;j++)
			 m[i][j]=c[i][j];
}
int main(){
	int i,et,n;
	FILE*f=fopen("iepuri.in","rt");
	FILE*g=fopen("iepuri.out","wt");
	fscanf(f,"%d",&et);
	while(et!=0){
		et--;
		fscanf (f, "%d %d %d %d %d %d %d " ,&x,&y,&z,&a,&b,&c,&n) ;
		initm();
		initrez();
		m[2][0]=c;
		m[2][1]=b;
		m[2][2]=a;
		for(i=0;(1<<i)<=n;i++){
			if(((1<<i)&n)!=0)inmrez();
			inmm();
		}
		fprintf (g, "%lld\n" ,(x * rez[0][0]+y*rez[0][1]+z*rez[0][2])%nr ) ;
		//g<<(x*rez[0][0]+y*rez[0][1]+z*rez[0][2])%nr;
		
	}
}