#include<stdio.h>
long x[4][4],y[4][4],x1,y1,z1,a,b,c,sc,t,i,g;
long n,start;
void inmul (long q[4][4],long w[4][4])
{
long i,j,z,c[4][4];
long sum=0,o,p;
for(i=1;i<=3;i++)
  for(j=1;j<=3;j++)
{     sum=0;
	for(z=1;z<=3;z++)
	  { o=q[i][z];
		p=w[z][j];
	   sum=(sum+(long long)o*p)%666013;
	  }
c[i][j]=sum;
}
for(i=1;i<=3;i++)
  for(j=1;j<=3;j++)
	 q[i][j]=c[i][j];

}
long form()
{
long start,i,j;
long sum;
x[1][1]=0;x[2][1]=1;x[3][1]=0;
x[1][2]=0;x[2][2]=0;x[3][2]=1;
x[1][3]=a;x[2][3]=b;x[3][3]=c;
n-=2;
start=1;
while(1)
{
if(start*2<=n)
 inmul(x,x);
else
   {
	if(sc==1)
   {
	 inmul(y,x);
   }
   else
	{
	for(i=1;i<=3;i++)
	 for(j=1;j<=3;j++)
		y[i][j]=x[i][j];
	}

	 x[1][1]=0;x[1][2]=1;x[1][3]=0;
	 x[2][1]=0;x[2][2]=0;x[2][3]=1;
	x[3][1]=a;x[3][2]=b;x[3][3]=c;
	n=n-start;
	}
if(start==n)
{
if(sc)
   inmul(y,x);
else
   {
	for(i=1;i<=3;i++)
	  for(j=1;j<=3;j++)
		 y[i][j]=x[i][j];
   }
break;
}

}  //while */
sum=(long long)(x1*y[1][3])%666013;
sum=sum+(long long)(y1*y[2][3])%666013;
sum=sum+(long long)(z1*y[3][3])%666013;
return sum%666013;
}//form
int main ()
{
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
scanf("%d",&t);
for(i=1;i<=t;i++)
{
 scanf("%d%d%d%d%d%d%ld",&x1,&y1,&z1,&a,&b,&c,&n);
g=form();
printf("%ld",g);
}
return 0;
}