#include<fstream.h>
#define m 666013
ifstream f("iepuri.in");
ofstream g("iepuri.out");
int init[3][3],p,sol[3][3],mat[3][3],iep[3][3];
int I[3][3];
int m3[3][3],x,y,z,a,b,c,n,t;

void multiply(int m1[3][3],int m2[3][3])
{
 int i,j,k;
 for(i=0;i<3;i++)
	for(j=0;j<3;j++)
		m3[i][j]=0;
 for(i=0;i<3;i++)
	for(j=0;j<3;j++)
		for(k=0;k<3;k++)
			m3[i][j]+=m1[i][k]*m2[k][j];
 for(i=0;i<3;i++)
	for(j=0;j<3;j++)
		m3[i][j]=m3[i][j]%m;
}

int main()
{
 int c1,c2,q,w,j,nr;
 f>>t;
 for(nr=0;nr<t;nr++)
 {
    f>>mat[0][0]>>mat[0][1]>>mat[0][2]>>iep[0][0]>>iep[1][0]>>iep[2][0]>>n;
    mat[1][0]=mat[2][1]=1;
    n=n-2;
    for(q=0;q<3;q++)
	for(w=0;w<3;w++)
		if(q==w)
			sol[q][w]=1;
		else
			sol[q][w]=0;
    for(j=31;j>=0;j--)
    {
	multiply(sol,sol);
	for(c1=0;c1<3;c1++)
		for(c2=0;c2<3;c2++)
			sol[c1][c2]=m3[c1][c2];
	if((1<<j&n) !=0)
	{	multiply(sol,mat);
		for(c1=0;c1<3;c1++)
			for(c2=0;c2<3;c2++)
				sol[c1][c2]=m3[c1][c2];
	}
    }
    multiply(sol,iep);
 g<<m3[0][0]<<'\n';
 }
 return 0;
}