#include<stdio.h>
unsigned long long int T,a0,b0,c0,a1,b1,c1,a2,b2,c2,a3,b3,c3,n,a4,b4,c4,
d4,d3,d2,d1,d0,e,p,a[33],b[33],c[33],i,x,y,z,x0,x1,x2,x3,x4;
int main()
{
	FILE *f,*g;
	f=fopen("iepuri.in","r");
	g=fopen("iepuri.out","w");
	fscanf(f,"%lld",&T);
	a0=0;b0=0;c0=1;
	a1=0;b1=1;c1=0;
	e=0;p=1;a[e]=a1;b[e]=b1;c[e]=c1;
	a2=1;b2=0;c2=0;
	e=1;p=2;a[e]=a2;b[e]=b2;c[e]=c2;
	for(i=1;i<=T;i++)
	{ fscanf(f,"%lld%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a3,&b3,&c3,&n);
	  a4=(a3*a3+b3)%666013;
	  b4=(a3*b3+c3)%666013;
	  c4=(a3*c3)%666013;
	  e=2;p=4;a[e]=a4;b[e]=b4;c[e]=c4;p*=2;
	  for(e=2;p<=n;e++)
	  {
	    d4=(a[e]*a[e])%666013;
	    d3=(2*a[e]*b[e])%666013;
	    d2=(2*a[e]*c[e]+b[e]*b[e])%666013;
	    d1=(2*b[e]*c[e])%666013;
	    d0=(c[e]*c[e])%666013;
	    a[e+1]=(d4*a4+d3*a3+d2*a2+d1*a1+d0*a0)%666013;
	    b[e+1]=(d4*b4+d3*b3+d2*b2+d1*b1+d0*b0)%666013;
	    c[e+1]=(d4*c4+d3*c3+d2*c2+d1*c1+d0*c0)%666013;
	    p*=2;
	  }
	  x0=x;x1=y;x2=z;
	  x3=(a3*x2+b3*x1+c3*x0)%666013;
	  x4=(a3*x3+b3*x2+c3*x1)%666013;
	  e=0;
	  while(n)
	  {     if(n%2)
		{
		  x0=(a[e]*x2+b[e]*x1+c[e]*x0)%666013;
		  x1=(a[e]*x3+b[e]*x2+c[e]*x1)%666013;
		  x2=(a[e]*x4+b[e]*x3+c[e]*x2)%666013;
		  x3=(a3*x2+b3*x1+c3*x0)%666013;
		  x4=(a3*x3+b3*x2+c3*x1)%666013;
		}
		n/=2;e++;
	  }
	  fprintf(g,"%lld\n",x0);
	}
	fcloseall();
	return 0;
}