#include<fstream.h>
#define m 666013
ifstream f("iepuri.in");
ofstream g("iepuri.out");
unsigned long st,aux,sp,n,x,y,z,a,b,c,nr;
int main()
{
 f>>nr;
 while(nr>0)
   {
     st=0;
     sp=0;
     f>>x>>y>>z>>a>>b>>c>>n;
     while(n>=3)
       {
	 sp=a*z+b*y+c*x;
	 aux=sp;
	 x=y;y=z;z=aux;
	 n--;
       }

    g<<sp%m<<"\n";
    nr--;
  }
 f.close();
 g.close();
 return 0;
}