#include <stdio.h>

#define ct 666013

void inmultire(long a[][3], long b[][3],long s[][3],int l1,int c1,int c2){
	int i,j,k;
	long c[3][3];
	for (i=0;i<l1;i++)
		for (j=0;j<c2;j++)
			c[i][j]=0;
	for (i=0;i<l1;i++)
		for (j=0;j<c2;j++){
			for (k=0;k<c1;k++)
				c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%ct)%ct;
		}
	for (i=0;i<l1;i++)
		for (j=0;j<c2;j++)
			s[i][j]=c[i][j];
}
	

int main(){
	int i,j,k;
	long a[3][3],s[3][3],T,X,Y,Z,A,B,C,N;
	FILE *fin=fopen("iepuri.in","r");
	FILE *fout=fopen("iepuri.out","w");
	fscanf(fin,"%d",&T);
	for (i=1;i<=T;i++){
		fscanf(fin,"%d %d %d %d %d %d %d",&X,&Y,&Z,&A,&B,&C,&N);
		a[0][0]=a[0][2]=a[1][0]=a[1][1]=0;
		a[0][1]=a[1][2]=1;
		a[2][0]=C;a[2][1]=B;a[2][2]=A;
		for (j=0;j<3;j++)
			for (k=0;k<3;k++)
				s[j][k]=0;
		s[0][0]=s[1][1]=s[2][2]=1;
		N-=2;
		do{
			if (N%2)
				inmultire(a,s,s,3,3,3);
			inmultire(a,a,a,3,3,3);
			N/=2;
		}
		while (N);
		a[0][0]=X;a[1][0]=Y;a[2][0]=Z;
		inmultire(s,a,s,3,3,1);
		fprintf(fout,"%d\n",s[2][0]);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}