#include <fstream>
using namespace std;

const int Mod = 666013;

int T,X,Y,Z,A,B,C,N;
int M[4][4],Mat[4][4];

ifstream F("iepuri.in");
ofstream G("iepuri.out");

void Get(int A[4][4],int B[4][4])
{
	for (int i=1;i<4;++i)
		for (int j=1;j<4;++j)
			B[i][j]=A[i][j];
}

void Inm(int A[4][4],int B[4][4])
{
	int C[4][4];
	for (int i=1;i<4;++i)
		for (int j=1;j<4;++j)
		{
			C[i][j]=0;
			for (int k=1;k<4;++k)
				C[i][j]+=(A[i][k]*B[k][j])%Mod;
			C[i][j]%=Mod;
		}
	for (int i=1;i<4;++i)
		for (int j=1;j<4;++j)
			A[i][j]=C[i][j];
}

void Pwr(int A[4][4],int pwr)
{
	if ( pwr==1 ) return;
	
	int B[4][4],C[4][4];
	Get(A,B);
	Get(A,C);
	
	Pwr(B,pwr/2);

	Get(B,A);
	Inm(A,A);
	
	if ( pwr%2 ) Inm(A,C);
}

void Print( int A[4][4] )
{
	G<<A[1][3]+2<<'\n';
}

int main()
{
	for (F>>T;T;--T)
	{
		F>>X>>Y>>Z>>A>>B>>C>>N;
		
		Mat[1][1]=X,Mat[1][2]=Y,Mat[1][3]=Z;
		for (int i=1;i<4;++i)
			for (int j=1;j<4;++j)
				M[i][j]=0;
		M[1][2]=M[2][3]=1;
		M[3][1]=C,M[3][2]=A,M[3][3]=B;
		
		Pwr( M , N-2 );
		Inm( Mat , M );
		Print( Mat );
	}
}