#include<cstdio>
int pp[4][4],A[4][4],x,y,z,a,b,c,n,p1,p2;
void prod(int X1[4][4],int X2[4][4])
{
	int X3[4][4];
	for(int i=1;i<=3;++i)
		for(int j=1;j<=3;++j)
		{
			X3[i][j]=0;
			for(int k=1;k<=3;++k)
				X3[i][j]=(X3[i][j]+(long long)((long long)(X1[i][k]%666013)*(long long)(X2[k][j]%666013))%666013)%666013;
		}
	for(int i=1; i<=3; ++i)
		for(int j=1; j<=3; ++j)
			X1[i][j]=X3[i][j];
}
void pz(int p)
{
	pp[1][1]=1; pp[1][2]=0; pp[1][3]=0; pp[2][1]=0; pp[2][2]=1; pp[2][3]=0; pp[3][1]=0; pp[3][2]=0; pp[3][3]=1;
	A [1][1]=a; A [1][2]=b; A [1][3]=c; A [2][1]=1; A [2][2]=0; A [2][3]=0; A [3][1]=0; A [3][2]=1; A [3][3]=0;
	while(p)
	{
		if(p%2==1)
		{
			prod(pp,A); //pepe
			// PEPE PE, PE PEPE!
		}
		prod(A,A);
		p/=2;
	}
	int cc[4][4]; 
	cc[1][1]=z; cc[1][2]=0; cc[1][3]=0; cc[2][1]=y; cc[2][2]=0; cc[2][3]=0; cc[3][1]=x; cc[3][2]=0; cc[3][3]=0;
	prod(pp,cc);
	printf("%d\n",pp[3][1]);
}
int main()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	scanf("%d",&p1);
	for(int p2=1; p2<=p1;++p2)
	{
		scanf("%d%d%d%d%d%d%d",&a,&b,&c,&x,&y,&z,&n);
		pz(n); //PEPE
	}
	//AXE THROWERS, HURL FASTER!
	return 0;
}