#include<iostream.h>
#include<fstream.h>
main()
{
long long ret,t,x,y,z,a,b,c,n,i,j,k,l,sp,aux,valid,s1,s2,s3;
fstream f("iepuri.in",ios::in);
fstream g("iepuri.out",ios::out);
f>>t;
ret=1;
do{
   sp=3;
   f>>x; f>>y; f>>z;
   f>>a; f>>b; f>>c;
   f>>n;
   if(n==1)g<<x<<endl;
   if(n==2)g<<y<<endl;
   if(n==3)g<<z<<endl;
   if(n>3){
     do{
	s1=z*a;
	s2=y*b;
	s3=x*c;
	k=s1+s2+s3;
//	if(k>666013)k%=666013;
	x=y; y=z; z=k;
	sp++;
       }while(sp<=n);
     x=k%666013;
     g<<x;
     if(ret<t)g<<endl;
	   }
   ret++;
   }while(ret<=t);

f.close();
g.close();
}