#include<fstream> 
#define M 666013 
#define Ai unsigned int 
#define ALL unsigned long long
using namespace std;
ifstream f("iepuri.in"); 
ofstream g("iepuri.out"); 
typedef ALL mat[3][3]; 
mat Z,X,Y,fin; 
int a,b,c,x,y,z,n,teste;
void prodmat(mat A,mat B,mat C) 
{
	int i,j,k;  
	for(i=0;i<=2;i++)      
		for(j=0;j<=2;j++)         
		{
			C[i][j]=0;         
			for(k=0;k<=2;k++) 
				C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%M)%M;         
		} 
}
void putere(mat A,mat B,Ai y)
{
	mat t,z;
	if(y==1)
		{
			B[0][0]=a;
			B[0][1]=b;
			B[0][2]=c;
			B[1][0]=B[2][1]=1;
			B[1][1]=B[1][2]=B[2][0]=B[2][2]=0;
		}
	else 
		if(y%2)  
		{
			putere(A,t,y/2); 
			prodmat(t,t,z); 
			prodmat(z,A,B);
		}
		else 
		{
			putere(A,t,y/2); 
			prodmat(t,t,B);
		} 
}   
int main()
{
	f>>teste;
	for(int i=1;i<=teste;i++)
	{
		f>>x>>y>>z>>a>>b>>c>>n;
		Y[0][0]=z;
		Y[1][0]=y;
		Y[2][0]=x;
		Z[0][0]=a;
		Z[0][1]=b;
		Z[0][2]=c;
		Z[1][0]=Z[2][1]=1;
		Z[1][1]=Z[1][2]=Z[2][0]=Z[2][2]=0;
		putere(Z,X,n-2); 
		prodmat(X,Y,fin);
		g<<fin[0][0]<<"\n";
	}
	return 0; 
}