#include<stdio.h>
int u[3][3],v[3][3],n,a,b,c,x,y,z,vv[3][3];
void copiere(int dest[3][3],int sursa[3][3]){
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			dest[i][j]=sursa[i][j];
}
void scrie(int aa[3][3]){
	int i,j;
	for(i=0;i<3;++i){
		for(int j=0;j<3;++j)
			printf("%10d",aa[i][j]);
		printf("\n");
	}
	printf("\n");
}
void citire(){
	scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
	u[0][0]=x;
	u[0][1]=y;
	u[0][2]=z;
	v[0][0]=v[0][1]=v[1][1]=v[2][0]=0;
	v[1][0]=v[2][1]=1;
	v[0][2]=c;
	v[1][2]=b;
	v[2][2]=a;
	//scrie(u);
	//scrie(v);
	copiere(vv,v);
	copiere(v,u);
}
void produs(int aa[3][3],int bb[3][3]){
	int i,j,k,cc[3][3];
	for(i=0;i<3;++i)
		for(j=0;j<3;++j){
			cc[i][j]=0;
			for(k=0;k<3;++k){
				cc[i][j]=cc[i][j]+(aa[i][k]*bb[k][j])%666013;
				if(cc[i][j]>=666013)
					cc[i][j]-=666013;
			}
		}
	copiere(aa,cc);
}
void putere(int n){
	//scrie(vv);
	if(n==0)
		return;
	if(n&1)
		produs(v,vv);
	produs(vv,vv);
	putere(n>>1);
}
int main(){
	int t;
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	scanf("%d",&t);
	while(t){
		citire();
		putere(n);
		printf("%d\n",v[0][0]);
		--t;
	}
	return 0;
}