#include<stdio.h>
FILE *f=fopen("iepuri.in","r"), *g=fopen("iepuri.out","w");
unsigned long long a[32][4][4],N,M[4][4],D[4][4],E[4][4];
unsigned int A,B,C,X,Y,Z,m,i,j,q,T,k;
bool bin[33];
void matrici(int p)
{
	
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
		{
			a[p][i][j]=0;
			for(int k=1;k<=3;k++)
				a[p][i][j]+=a[p-1][i][k]*a[p-1][k][j];
			a[p][i][j]%=666013;
		}
}		
void xmatrici(int p)
{
	int i,j;
	for(i=1;i<=3;i++)
		for( j=1;j<=3;j++)
		{
			D[i][j]=0;
			for(int k=1;k<=3;k++)
				D[i][j]+=M[i][k]*a[p][k][j];
			D[i][j]%=666013;
		}
	for(i=1;i<=3;i++)
		for(j=1;j<=3;j++) M[i][j]=D[i][j];
}
void fmatrici()
{
	for(int i=1;i<=3;i++)
		for(int j=1;j<=1;j++)
		{
			D[i][j]=0;
			for(int k=1;k<=3;k++)
				D[i][j]+=M[i][k]*E[k][j];
			D[i][j]%=666013;
		}
}
int main()
{
	fscanf(f,"%d", &T);
	for(i=1;i<=T;i++)
	{
		for(i=0;i<=32;i++)
			for(j=0;j<=3;j++) 
				for(k=0;k<=3;k++) a[i][j][k]=0;
		for(i=0;i<=3;i++)
			for(j=0;j<=3;j++)
				M[i][j]=D[i][j]=E[i][j]=0;
		
		fscanf(f,"%d %d %d %d %d %d %d",&X,&Y,&Z,&A,&B,&C,&N);
		a[0][1][2]=1;
		a[0][2][3]=1;
		a[0][3][1]=C;
		a[0][3][2]=B;
		a[0][3][3]=A;
		
		q=0;
		while(N)
		{
			bin[q++]=N%2;
			N/=2;
		}
		for(i=1;i<q;i++) matrici(i);
		
		M[1][1]=1;
		M[2][2]=1;
		M[3][3]=1;
		
		for(j=0;j<q;j++) 
			if(bin[j]) xmatrici(j);
		
		E[1][1]=X;
		E[2][1]=Y;
		E[3][1]=Z;
		
		fmatrici();
		
		fprintf(g,"%ld\n",D[1][1]%666013);
	}	
		fclose(g);
		return 0;
}