#include<stdio.h>
main()
{
long long ret,t,x,y,z,a,b,c,n,i,j,k,l,sp,aux,valid,s1,s2,s3;
freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
fscanf(stdin,"%lld",&t);
ret=1;
do{
   sp=3;
   fscanf(stdin,"%lld%lld%lld",&x,&y,&z);
   fscanf(stdin,"%lld%lld%lld",&a,&b,&c);
   fscanf(stdin,"%lld",&n);
   if(n==1)fprintf(stdout,"%lld\n",x);
   if(n==2)fprintf(stdout,"%lld\n",x);
   if(n==3)fprintf(stdout,"%lld\n",x);
   if(n>3){
     do{
	s1=z*a;
	s2=y*b;
	s3=x*c;
	k=s1+s2+s3;
	k%=666013;
	x=y; y=z; z=k;
	sp++;
       }while(sp<=n);
     x=k%666013;
     fprintf(stdout,"%lld\n",x);
      }
   ret++;
   }while(ret<=t);

fclose(stdin);
fclose(stdout);
}