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

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

int main()
{
 long long c1,c2,q,w,j,nr;
 f>>t;
 for(nr=0;nr<t;nr++)
 {
    f>>iep[2][0]>>iep[1][0]>>iep[0][0]>>mat[0][0]>>mat[0][1]>>mat[0][2]>>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;
}