# include <fstream>
# define MODULO 666013

using namespace std;

ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");

int x,y,z,a,b,c,n,T,Teste;
long long A[5][5],B[5][5],C[5][5];
long long S[5][5],R[5][5];

void inmult (long long A[5][5],long long B[5][5], int na, int ma, int nb, int mb, long long C[5][5])
{
	long long ia,ib,ja,jb;
	for(ia=1;ia<=na;ia++)
		for (jb=1;jb<=mb;jb++)
			C[ia][jb]=0;
	for (ia=1;ia<=na;ia++)
		for (jb=1;jb<=mb;jb++)
		{
			for (ib=1;ib<=nb;ib++)
			{
				C[ia][jb]=(C[ia][jb]+(A[ia][ib]*B[ib][jb])%MODULO)%MODULO;
			}
		}
		
}

void putere (int x, long long B[5][5])
{
	int i,j;
	if (x==1)
	{
		for (i=1;i<=3;i++)
			for (j=1;j<=3;j++)
				B[i][j]=A[i][j];
		return;
	}
	if(x==2)
	{
		inmult (A,A,3,3,3,3,B);
		return;
	}
	putere (x/2,B);
	for (i=1;i<=3;i++)
		for (j=1;j<=3;j++)
			C[i][j]=B[i][j];
	inmult (C,C,3,3,3,3,B);
	if (x%2==1)
	{
		for (i=1;i<=3;i++)
		for (j=1;j<=3;j++)
			C[i][j]=B[i][j];
		inmult (C,A,3,3,3,3,B);
	}
}

int main ()
{
	fin>>Teste;
	for (T=1;T<=Teste;T++)
	{
		fin>>S[1][3]>>S[1][2]>>S[1][1];
		fin>>a>>b>>c;
		fin>>n;
		if (n==1)
			fout<<x<<'\n';
		else if (n==2)
			fout<<y<<'\n';
		else if (n==3)
			fout<<z<<'\n';
		else
		{
			A[1][1]=a;A[1][2]=1;A[3][1]=c;
			A[2][1]=b;A[2][3]=1;
			putere(n-2,B);
			inmult(S,B,1,3,3,3,R);
			fout<<R[1][1]<<'\n';
		}
	}
	return 0;
}