#include<fstream.h>
int main()   
{   
 ifstream f("iepuri.in");   
 ofstream g("iepuri.out");   
 long long t,x,y,z,a,b,c,n,i,j,r;   
 f>>t;   
 for(i=1;i<=t;i++)   
  {   
   f>>x>>y>>z>>a>>b>>c>>n;   
   for(j=1;j<=n-2;j++)   
    {   
     r=a*z+b*y+c*x;   
     x=y;y=z;z=r;   
    }
 if(z>666013) 
   z=z%666013;
 g<<z;

  }
 return 0;   
}