#include<stdio.h>
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,as,bs,cs,sol,e,p,a[33],b[33],c[33],i,x,y,z;
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);
	  e=2;p=4;a[e]=a4;b[e]=b4;c[e]=c4;
	  while(p<n)
	  {
	    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;
	    e++;p*=2;
	    a[e]=(d4*a4+d3*a3+d2*a2+d1*a1+d0*a0)%666013;
	    b[e]=(d4*b4+d3*b3+d2*b2+d1*b1+d0*b0)%666013;
	    c[e]=(d4*c4+d3*c3+d2*c2+d1*c1+d0*c0)%666013;
	  }
	  as=a0;bs=b0;cs=c0;e=-1;
	  while(n)
	  {     e++;
		if(n%2)
		{
		 d4=(a[e]*as)%666013;
		 d3=(a[e]*bs+b[e]*as)%666013;
		 d2=(a[e]*cs+b[e]*bs+c[e]*bs)%666013;
		 d1=(b[e]*cs+c[e]*bs)%666013;
		 d0=(c[e]*cs)%666013;
		 as=(d4*a4+d3*a3+d2*a2+d1*a1+d0*a0)%666013;
		 bs=(d4*b4+d3*b3+d2*b2+d1*b1+d0*b0)%666013;
		 cs=(d4*c4+d3*c3+d2*c2+d1*c1+d0*c0)%666013;
		}
		n/=2;
	  }
	  sol=(as*z+bs*y+cs*x)%666013;
	  fprintf(g,"%lld\n",sol);
	}
	fcloseall();
	return 0;
}